Submission #14236

#TimeUsernameProblemLanguageResultExecution timeMemory
14236dohyun0324사회적 불평등 (TOKI14_social)C++98
100 / 100
46 ms14364 KiB
#include<stdio.h> #include<algorithm> using namespace std; int n,t; long long dap; struct data{ int x,y; bool operator<(const data&r)const{ return x<r.x; } }a[100010]; struct data2 { long long val1,val2,val3,val4; }tree[400010]; void update(int pos,int p) { int x=a[pos].y; while(x<=t) { tree[x].val1+=p*a[pos].x*a[pos].y; tree[x].val2+=p*a[pos].x; tree[x].val3+=p*a[pos].y; tree[x].val4+=p; x+=x&(-x); } } long long query(int x,int a,int b) { long long s=0; while(x) { s+=tree[x].val1-b*tree[x].val2-a*tree[x].val3+a*b*tree[x].val4; x-=x&(-x); } return s; } int main() { int i,maxi=0; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d %d",&a[i].x,&a[i].y); if(maxi<a[i].y) maxi=a[i].y; } for(t=1;t<=maxi;t*=2); sort(a+1,a+n+1); for(i=1;i<=n;i++) { update(i,1); } for(i=1;i<=n;i++) { update(i,-1); dap+=query(a[i].y,a[i].x,a[i].y); dap+=-(query(t,a[i].x,a[i].y)-query(a[i].y,a[i].x,a[i].y)); } printf("%lld",-dap); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...