Advertisement
Guest User

Untitled

a guest
May 8th, 2014
528
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.75 KB | None | 0 0
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<algorithm>
  4. #include<set>
  5. #include<map>
  6. #include<queue>
  7. #include<stack>
  8. #include<deque>
  9. #include<vector>
  10. #include<string>
  11. #include<math.h>
  12. using namespace std;
  13.  
  14. #define INF 1000000000
  15. #define lint long long
  16. #define pb push_back
  17. #define mp make_pair
  18. #define MOD 1000000007
  19.  
  20. pair <lint,lint> a[100005];
  21. lint prod[100005];
  22. lint t[33000],t1[33000],tp[33000],tv[33000];
  23.  
  24. void update(int v,lint val)
  25. {
  26. t[v]+=val;
  27. t1[v]++;
  28. v/=2;
  29. while(v)
  30. {
  31. t[v]=t[2*v]+t[2*v+1];
  32. t1[v]=t1[2*v]+t1[2*v+1];
  33. v/=2;
  34. }
  35. }
  36. void update1(int v,lint val)
  37. {
  38. tp[v]+=val;
  39. v/=2;
  40. while(v)
  41. {
  42. tp[v]=tp[2*v]+tp[2*v+1];
  43. v/=2;
  44. }
  45. }
  46. void update2(int v,lint val)
  47. {
  48. tv[v]+=val;
  49. v/=2;
  50. while(v)
  51. {
  52. tv[v]=tv[2*v]+tv[2*v+1];
  53. v/=2;
  54. }
  55. }
  56. lint get(int v,int li,int ri,int l,int r)
  57. {
  58. if(li>r||ri<l)
  59. return 0;
  60. if(li>=l&&ri<=r)
  61. return t[v];
  62. return get(2*v,li,(li+ri)/2,l,r)+get(2*v+1,(li+ri)/2+1,ri,l,r);
  63. }
  64. lint gett1(int v,int li,int ri,int l,int r)
  65. {
  66. if(li>r||ri<l)
  67. return 0;
  68. if(li>=l&&ri<=r)
  69. return t1[v];
  70. return gett1(2*v,li,(li+ri)/2,l,r)+gett1(2*v+1,(li+ri)/2+1,ri,l,r);
  71. }
  72. lint getp(int v,int li,int ri,int l,int r)
  73. {
  74. if(li>r||ri<l)
  75. return 0;
  76. if(li>=l&&ri<=r)
  77. return tp[v];
  78. return getp(2*v,li,(li+ri)/2,l,r)+getp(2*v+1,(li+ri)/2+1,ri,l,r);
  79. }
  80. lint getv(int v,int li,int ri,int l,int r)
  81. {
  82. if(li>r||ri<l)
  83. return 0;
  84. if(li>=l&&ri<=r)
  85. return tv[v];
  86. return getv(2*v,li,(li+ri)/2,l,r)+getv(2*v+1,(li+ri)/2+1,ri,l,r);
  87. }
  88. int main()
  89. {
  90. int n,i,j,p=16384;
  91. scanf("%d",&n);
  92. for(i=1;i<=n;++i)
  93. {
  94. scanf("%lld %lld",&a[i].first,&a[i].second);
  95. }
  96. sort(a+1,a+1+n);
  97. for(i=1;i<=n;++i)
  98. {
  99. prod[i]=a[i].first*a[i].second;
  100. }
  101. lint ans=0;
  102. for(i=1;i<=n;++i)
  103. {
  104. lint sum1,sum2,cntpoqr,cntmec=0,sumprpoqr,sumprmec;
  105.  
  106. cntpoqr=gett1(1,p,p+p-1,p,a[i].second+p-1);
  107. cntmec=gett1(1,p,p+p-1,a[i].second+p,p+p-1);
  108.  
  109. sumprpoqr=get(1,p,p+p-1,p,a[i].second+p-1);
  110. sumprmec=get(1,p,p+p-1,a[i].second+p,p+p-1);
  111.  
  112. sum1=a[i].first*(cntpoqr*a[i].second-sumprpoqr);
  113. sum1+=a[i].first*(sumprmec-cntmec*a[i].second);
  114.  
  115. sum2=-getv(1,p,p+p-1,a[i].second+p,p+p-1)*a[i].second+getp(1,p,p+p-1,a[i].second+p,p+p-1);
  116. sum2+=getv(1,p,p+p-1,p,a[i].second+p-1)*a[i].second-getp(1,p,p+p-1,p,a[i].second+p-1);
  117.  
  118. ans+=sum1-sum2;
  119.  
  120. update(a[i].second+p-1,a[i].second);
  121. update1(a[i].second+p-1,prod[i]);
  122. update2(a[i].second+p-1,a[i].first);
  123.  
  124. }
  125. cout<<ans;
  126. return 0;
  127. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement