제출 #137426

#제출 시각아이디문제언어결과실행 시간메모리
137426jangwonyoung이상적인 도시 (IOI12_city)C++14
100 / 100
68 ms14612 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; #define fi first #define se second #define xx fi.fi #define yy fi.se const ll mod=1e9;//diu wtf const int N=2e5+1,M=2e5+1; void add(ll& x,ll y){ x+=y; if(x<0) x+=mod; if(x>=mod) x-=mod; } int n,m; pair<pii,int>a[N]; pair<pii,int>b[N]; int l[M],r[M];//node range int nd[N]; int par[M]; int find(int x){ if(par[x]!=x) par[x]=find(par[x]); return par[x]; } vector<int>adj[M]; int sz[M]; void join(int x,int y){ if(find(x)==find(y)) return; par[find(x)]=find(y); adj[x].push_back(y); adj[y].push_back(x); } ll ans=0; ll val[N]; void dfs(int id,int p){ sz[id]=r[id]-l[id]+1; //cout << id << ' ' << p << endl; for(auto cur:adj[id]){ if(cur==p) continue; dfs(cur,id); sz[id]+=sz[cur]; } } void dfs2(int id,int p){ for(auto cur:adj[id]){ if(cur==p) continue; dfs2(cur,id); int cl=l[cur]; while(a[cl].yy<a[l[id]].yy){ add(ans,val[cl]*(n-sz[cur])%mod); val[cl+1]+=val[cl]; val[cl]=0; cl++; } int cr=r[cur]; while(a[cr].yy>a[r[id]].yy){ add(ans,val[cr]*(n-sz[cur])%mod); add(val[cr-1],val[cr]); val[cr]=0; cr--; } ll duh=0; int jj=a[cl].yy-a[l[id]].yy+l[id]; for(int i=cl; i<=cr ;i++){ add(ans,-duh*(sz[cur]-duh)%mod); duh+=val[i]; val[jj]+=val[i]; jj++; } add(ans,1LL*sz[cur]*(n-sz[cur])%mod);//advance } for(int i=l[id]; i<=r[id] ;i++) val[i]++; ll duh=0; for(int i=l[id]; i<=r[id] ;i++){ add(ans,duh*(sz[id]-duh)%mod); add(duh,val[i]); } } int DistanceSum(int N, int *X, int *Y){ n=N; for(int i=1 ;i<=n ;i++) a[i]={{X[i-1],Y[i-1]},i}; sort(a+1,a+n+1); for(int i=1; i<=n ;i++){ a[i].se=i;b[i]=a[i]; swap(b[i].fi.se,b[i].fi.fi); if(i!=1 && a[i].fi.fi==a[i-1].fi.fi && a[i].fi.se==a[i-1].fi.se+1) r[m]=i; else{ m++;l[m]=r[m]=i; } nd[i]=m; } sort(b+1,b+n+1); for(int i=1; i<=m ;i++) par[i]=i; for(int i=1; i<=n ;i++){ if(i!=1 && b[i].fi.fi==b[i-1].fi.fi && b[i].fi.se==b[i-1].fi.se+1) join(nd[b[i].se],nd[b[i-1].se]); } dfs(1,0); dfs2(1,0); 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...