Submission #401601

#TimeUsernameProblemLanguageResultExecution timeMemory
401601JasiekstrzIdeal city (IOI12_city)C++17
100 / 100
55 ms17112 KiB
#include<bits/stdc++.h> #define fi first #define se second using namespace std; const int NN=1e5; const int MOD=1e9; struct Node { long long id; long long l,r; long long x; }; pair<long long,long long> t[NN+10]; vector<Node> tab; vector<int> e[NN+10]; vector<long long> w[NN+10]; vector<long long> siz[NN+10]; void mknode(int l,int r) { //cerr<<"Node"<<tab.size()<<": x="<<t[l].fi<<" l="<<t[l].se<<" r="<<t[r].se<<"\n"; w[tab.size()].resize(r-l+1); siz[tab.size()].resize(r-l+1); tab.push_back({tab.size(),t[l].se,t[r].se,t[l].fi}); return; } long long merge(int x,int y) // merge y to x { //cerr<<"merge Node"<<y<<" to Node"<<x<<": "; long long ans=0; int bi=max(0LL,tab[y].l-tab[x].l),bj=max(0LL,tab[x].l-tab[y].l); int ei=bi+min(w[x].size()-bi,w[y].size()-bj),ej=bj+min(w[x].size()-bi,w[y].size()-bj); //cerr<<"bi="<<bi<<" ei="<<ei<<" bj="<<bj<<" ej="<<ej<<" "; for(int i=0;i<bj;i++) { w[y][i+1]=(w[y][i+1]+siz[y][i]+w[y][i])%MOD; siz[y][i+1]=(siz[y][i+1]+siz[y][i])%MOD; } for(int i=w[y].size()-1;i>=ej;i--) { w[y][i-1]=(w[y][i-1]+siz[y][i]+w[y][i])%MOD; siz[y][i-1]=(siz[y][i-1]+siz[y][i])%MOD; } // whole y is in x long long p=0,s=0,ps=0,ss=0; for(int i=0;i<bi;i++) { p=(p+ps+w[x][i])%MOD; ps=(ps+siz[x][i])%MOD; } for(int i=w[x].size()-1;i>=ei;i--) { s=(s+ss+w[x][i])%MOD; ss=(ss+siz[x][i])%MOD; } for(int i=bi,j=bj;i<ei && j<ej;i++,j++) { p=(p+ps+w[x][i])%MOD; ps=(ps+siz[x][i])%MOD; ans=(ans+p*siz[y][j]+w[y][j]*ps+ps*siz[y][j])%MOD; } for(int i=ei-1,j=ej-1;i>=bi && j>=bj;i--,j--) { s=(s+ss)%MOD; ans=(ans+s*siz[y][j]+w[y][j]*ss+ss*siz[y][j])%MOD; s=(s+w[x][i])%MOD; ss=(ss+siz[x][i])%MOD; } for(int i=bi,j=bj;i<ei && j<ej;i++,j++) { siz[x][i]=(siz[x][i]+siz[y][j])%MOD; w[x][i]=(w[x][i]+w[y][j]+siz[y][j])%MOD; } //for(int i=0;i<w[x].size();i++) // cerr<<"ww["<<i<<"]="<<w[x][i]<<" ss["<<i<<"]="<<siz[x][i]<<" "; //cerr<<"ans="<<ans<<"\n"; return ans; } long long dfs(int x,int p) { long long ans=0; long long tmp=0; for(int i=tab[x].l;i<=tab[x].r;i++) { tmp=(tmp+i-tab[x].l)%MOD; ans=(ans+tmp)%MOD; } fill(w[x].begin(),w[x].end(),0); fill(siz[x].begin(),siz[x].end(),1); for(auto v:e[x]) { if(v==p) continue; ans+=dfs(v,x); ans+=merge(x,v); ans%=MOD; } return ans; } int DistanceSum(int N,int *X,int *Y) { int n=N; for(int i=0;i<n;i++) t[i+1]={X[i],Y[i]}; sort(t+1,t+n+1); int bg=1; for(int i=1;i<=n;i++) { if(i!=1 && (t[i-1].fi!=t[i].fi || t[i-1].se+1!=t[i].se)) { mknode(bg,i-1); bg=i; } } mknode(bg,n); int m=tab.size(); for(int i=0,j=0;i<m;i++) { while(j<m && tab[j].x<tab[i].x && (tab[j].x<tab[i].x-1 || tab[j].r<tab[i].l)) j++; while(j<m && tab[j].x==tab[i].x-1 && tab[j].l<=tab[i].r) { //cerr<<"link Node"<<i<<" Node"<<j<<"\n"; e[i].push_back(j); e[j].push_back(i); j++; } if(j>0) j--; //cerr<<"after "<<i<<" "<<j<<"\n"; } long long ans=dfs(0,-1); return (ans+MOD)%MOD; }

Compilation message (stderr)

city.cpp: In function 'void mknode(int, int)':
city.cpp:23:25: warning: narrowing conversion of 'tab.std::vector<Node>::size()' from 'std::vector<Node>::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   23 |  tab.push_back({tab.size(),t[l].se,t[r].se,t[l].fi});
      |                 ~~~~~~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...