Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<stdio.h>
- #include<algorithm>
- #include<set>
- #include<map>
- #include<queue>
- #include<stack>
- #include<deque>
- #include<vector>
- #include<string>
- #include<math.h>
- using namespace std;
- #define INF 1000000000
- #define lint long long
- #define pb push_back
- #define mp make_pair
- #define MOD 1000000007
- pair <lint,lint> a[100005];
- lint prod[100005];
- lint t[33000],t1[33000],tp[33000],tv[33000];
- void update(int v,lint val)
- {
- t[v]+=val;
- t1[v]++;
- v/=2;
- while(v)
- {
- t[v]=t[2*v]+t[2*v+1];
- t1[v]=t1[2*v]+t1[2*v+1];
- v/=2;
- }
- }
- void update1(int v,lint val)
- {
- tp[v]+=val;
- v/=2;
- while(v)
- {
- tp[v]=tp[2*v]+tp[2*v+1];
- v/=2;
- }
- }
- void update2(int v,lint val)
- {
- tv[v]+=val;
- v/=2;
- while(v)
- {
- tv[v]=tv[2*v]+tv[2*v+1];
- v/=2;
- }
- }
- lint get(int v,int li,int ri,int l,int r)
- {
- if(li>r||ri<l)
- return 0;
- if(li>=l&&ri<=r)
- return t[v];
- return get(2*v,li,(li+ri)/2,l,r)+get(2*v+1,(li+ri)/2+1,ri,l,r);
- }
- lint gett1(int v,int li,int ri,int l,int r)
- {
- if(li>r||ri<l)
- return 0;
- if(li>=l&&ri<=r)
- return t1[v];
- return gett1(2*v,li,(li+ri)/2,l,r)+gett1(2*v+1,(li+ri)/2+1,ri,l,r);
- }
- lint getp(int v,int li,int ri,int l,int r)
- {
- if(li>r||ri<l)
- return 0;
- if(li>=l&&ri<=r)
- return tp[v];
- return getp(2*v,li,(li+ri)/2,l,r)+getp(2*v+1,(li+ri)/2+1,ri,l,r);
- }
- lint getv(int v,int li,int ri,int l,int r)
- {
- if(li>r||ri<l)
- return 0;
- if(li>=l&&ri<=r)
- return tv[v];
- return getv(2*v,li,(li+ri)/2,l,r)+getv(2*v+1,(li+ri)/2+1,ri,l,r);
- }
- int main()
- {
- int n,i,j,p=16384;
- scanf("%d",&n);
- for(i=1;i<=n;++i)
- {
- scanf("%lld %lld",&a[i].first,&a[i].second);
- }
- sort(a+1,a+1+n);
- for(i=1;i<=n;++i)
- {
- prod[i]=a[i].first*a[i].second;
- }
- lint ans=0;
- for(i=1;i<=n;++i)
- {
- lint sum1,sum2,cntpoqr,cntmec=0,sumprpoqr,sumprmec;
- cntpoqr=gett1(1,p,p+p-1,p,a[i].second+p-1);
- cntmec=gett1(1,p,p+p-1,a[i].second+p,p+p-1);
- sumprpoqr=get(1,p,p+p-1,p,a[i].second+p-1);
- sumprmec=get(1,p,p+p-1,a[i].second+p,p+p-1);
- sum1=a[i].first*(cntpoqr*a[i].second-sumprpoqr);
- sum1+=a[i].first*(sumprmec-cntmec*a[i].second);
- 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);
- 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);
- ans+=sum1-sum2;
- update(a[i].second+p-1,a[i].second);
- update1(a[i].second+p-1,prod[i]);
- update2(a[i].second+p-1,a[i].first);
- }
- cout<<ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement