fork download
  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
stdin
Standard input is empty
stdout
0