제출 #424679

#제출 시각아이디문제언어결과실행 시간메모리
424679Charis02이상적인 도시 (IOI12_city)C++14
0 / 100
116 ms3132 KiB
#include<iostream> #include<map> #include<vector> #include<set> #include<algorithm> #define pi pair < int,int > #define mp(a,b) make_pair(a,b) #define rep(i,a,b) for(int i = a;i < b;i++) #define MAXN 100004 using namespace std; int seg[4*MAXN][2]; int id[MAXN]; map < int,int > mapper; int mod = 1000000000; void update(int low,int high,int pos,int slow) { if(low==slow&&low==high) { seg[pos][0]++; seg[pos][1]+=id[slow]; return; } if(low>slow||high<slow) return; int mid = (low+high) / 2; update(low,mid,pos*2+1,slow); update(mid+1,high,pos*2+2,slow); rep(id,0,2) seg[pos][id] = (seg[pos*2+1][id] + seg[pos*2+2][id])%mod; return; } pi query(int low,int high,int pos,int slow,int shigh) { if(low >= slow && high <= shigh) return mp(seg[pos][0],seg[pos][1]); if(low>shigh||high<slow) return mp(0,0); int mid = (low+high)/2; pi q1 = query(low,mid,pos*2+1,slow,shigh); pi q2 = query(mid+1,high,pos*2+2,slow,shigh); q1.first = (q1.first+q2.first)%mod; q1.second = (q1.second+q2.second)%mod; return q1; } int DistanceSum(int N, int *X, int *Y) { vector < pi > points; set < int > ys; rep(i,0,N) { points.push_back(mp(X[i],Y[i])); ys.insert(Y[i]); } int cnt = 0; for(set < int >::iterator it = ys.begin();it != ys.end();it++) { id[cnt] = *it; mapper[*it] = cnt++; } sort(points.begin(),points.end()); int ans = 0; int sum = 0; rep(i,0,N) { int x = points[i].first; int y = mapper[points[i].second]; ans = (ans+x*i-sum)%mod; sum = (sum+x)%mod; //cout << "here " << x << " " << y << " " << ans << " -> "; pi q = query(0,cnt,0,0,y); ans = (ans + q.first*id[y] - q.second)%mod; q = query(0,cnt,0,y,cnt); ans = (ans - q.first*id[y] + q.second)%mod; update(0,cnt,0,y); // cout << "and here " << x << " " << y << " " << ans << endl; } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...