fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef pair<int,int> P;
  5. typedef long long ll;
  6.  
  7. int n;
  8. struct rect
  9. {
  10. 	int sort_y;
  11. 	ll x,y;
  12. }rec[100005];
  13. bool cmp_x(const rect& r1,const rect& r2)
  14. {
  15. 	return r1.x > r2.x;
  16. }
  17. bool cmp_y(const rect& r1,const rect& r2)
  18. {
  19. 	return r1.y < r2.y;
  20. }
  21. struct bit
  22. {
  23. 	ll bit[(1<<17)+5];
  24. 	void add(int pos,ll add)
  25. 	{
  26. 		for(int i=pos;i<=n;i+=i&-i) bit[i]+=add;
  27. 	}
  28. 	ll query(int pos)
  29. 	{
  30. 		ll res=0;
  31. 		for(int i=pos;i>0;i-=i&-i) res+=bit[i];
  32. 		return res;
  33. 	}
  34. }aibi,num,ai,bi;
  35. int main()
  36. {
  37. 	scanf("%d",&n);
  38. 	for(int i=0;i<n;i++)
  39. 	{
  40. 		scanf("%lld %lld",&rec[i].x,&rec[i].y);
  41. 	}
  42. 	sort(rec,rec+n,cmp_y);
  43. 	for(int i=0;i<n;i++) rec[i].sort_y = i;
  44. 	sort(rec,rec+n,cmp_x);
  45. 	ll res = 0LL;
  46.  
  47. 	for(int i=0;i<n;i++)
  48. 	{
  49. 		ll c = rec[i].x;
  50. 		ll d = rec[i].y;
  51. 		int id = rec[i].sort_y+1;
  52. 		ll v = num.query(n),v2 = num.query(id); v-=v2;
  53. 		ll sum_aibi = aibi.query(n),sum2_aibi = aibi.query(id); sum_aibi-=sum2_aibi;
  54. 		ll sum_ai = ai.query(n),sum2_ai = ai.query(id); sum_ai-=sum2_ai;
  55. 		ll sum_bi = bi.query(n),sum2_bi = bi.query(id); sum_bi-=sum2_bi;
  56.  
  57. 		//bigger
  58. 		res += sum_aibi + c*d*v - d*sum_ai - c*sum_bi;
  59. 		//smaller
  60. 		res += d*sum2_ai + c*sum2_bi - sum2_aibi - c*d*v2;
  61. 		num.add(id,1);
  62. 		aibi.add(id,c*d);
  63. 		ai.add(id,c);
  64. 		bi.add(id,d);
  65. 	}
  66.  
  67. 	printf("%lld\n",res);
  68. }
Success #stdin #stdout 0s 9352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/epj1sB
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!