Submission #70920

#TimeUsernameProblemLanguageResultExecution timeMemory
70920MANcityIdeal city (IOI12_city)C++14
55 / 100
218 ms24540 KiB
#include<iostream> #include<cstdio> #include<fstream> #include<algorithm> #include<cmath> #include<map> #include<queue> #include<set> #include<stack> #include<string> #include<cstring> #include<vector> using namespace std; #define for1(i,n) for(int i=1;i<=(int)n;i++) #define for0(i,n) for(int i=0;i<=(int)n;i++) #define forn(i,n) for(int i=n;i>=1;i--) #define fo(i,x,y) for(int i=x;i<=(int)y;i++) #define fr(i,x,y) for(int i=x;i>=(int)y;i--) #define pb push_back #define mp make_pair #define LL long long const LL Mod=1000*1000*1000+7; const LL maMod=1000*1000*1000; int N; int X[200002]; int Y[200002]; int dist[3002][3002]; int used[2002]; vector<vector<int> > g(3002); void bfs(int v) { int p_now=v; for0(i,N-1) used[i]=0; queue<int> myque; myque.push(v); while(!myque.empty()) { int v=myque.front(); for0(j,g[v].size()-1) { int to=g[v][j]; if(used[to]==0) { dist[p_now][to]=dist[p_now][v]+1; used[to]=1; myque.push(to); } } myque.pop(); } } pair<LL,int> Sx[100002]; pair<LL,int> Sy[100002]; int posx[100002]; int posy[100002]; pair<int,int> t[4*100002]; void update(int left,int right,int pos,int v,pair<int,int> val) { if(left==right) t[v]=val; else { int m=(left+right)/2; if(pos<=m) update(left,m,pos,2*v,val); else update(m+1,right,pos,2*v+1,val); t[v].first=(t[2*v].first+t[2*v+1].first); t[v].second=(t[2*v].second+t[2*v+1].second); } } pair<int,int> get(int left,int right,int l,int r,int v) { if(l>r) return {0,0}; if(left==l && right==r) return t[v]; int m=(left+right)/2; pair<int,int> A=get(left,m,l,min(r,m),2*v); pair<int,int> B=get(m+1,right,max(l,m+1),r,2*v+1); return {A.first+B.first,A.second+B.second}; } int DistanceSum(int N_0, int *X_0, int *Y_0) { N=N_0; for0(i,N-1) X[i]=X_0[i]; for0(i,N-1) Y[i]=Y_0[i]; if(N<=2000) { for0(i,N-1) for0(j,N-1) { if(i!=j) { int dist=abs(X[i]-X[j])+abs(Y[i]-Y[j]); if(dist==1) { g[i].push_back(j); } } } for0(i,N-1) bfs(i); LL sumdist=0; for0(i,N-1) fo(j,i+1,N-1) sumdist=(sumdist+dist[i][j])%Mod; /*cout<<sumdist<<endl; cout<<endl; cout<<endl; cout<<endl;*/ return sumdist; } for0(i,N-1) Sx[i]={X[i],i}; for0(i,N-1) Sy[i]={Y[i],i}; sort(Sx,Sx+N); sort(Sy,Sy+N); for0(i,N-1) posx[Sx[i].second]=i; for0(i,N-1) posy[Sy[i].second]=i; update(0,N-1,posy[Sx[0].second],1,{1,Y[Sx[0].second]}); LL SUM_X=Sx[0].first; LL SUM_DIST=0; for1(i,N-1) { SUM_DIST=(SUM_DIST+(LL)(i)*(LL)Sx[i].first)%maMod; SUM_DIST=(SUM_DIST-SUM_X+maMod+maMod)%maMod; int repos=Sx[i].second; int ypos=posy[repos]; pair<int,int> SUM_POQR=get(0,N-1,0,ypos-1,1); pair<int,int> SUM_MEC=get(0,N-1,ypos+1,N-1,1); int qan_poqr=SUM_POQR.first; int qan_mec=SUM_MEC.first; SUM_DIST=(SUM_DIST+(LL)qan_poqr*(LL)Y[repos]); SUM_DIST=(SUM_DIST-SUM_POQR.second+maMod+maMod)%maMod; SUM_DIST=(SUM_DIST-(LL)qan_mec*(LL)Y[repos]+maMod+maMod)%maMod; SUM_DIST=(SUM_DIST+SUM_MEC.second)%maMod; SUM_X=(SUM_X+Sx[i].first)%maMod; update(0,N-1,ypos,1,{1,Y[repos]}); } return (SUM_DIST+maMod)%maMod; } /* 5 1 1 1 2 2 2 2 3 3 3 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...