Submission #137426

#	Time	Username	Problem	Language	Result	Execution time	Memory
137426		jangwonyoung	Ideal city (IOI12_city)	C++14	100 / 100	68 ms	14612 KiB

city

#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;
}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45