oj.uz

Submission #137423

# Submission time Handle Problem Language Result Execution time Memory
137423 2019-07-27T17:48:11 Z jangwonyoung Ideal city (IOI12_city) C++14
32 / 100
 68 ms 12284 KB 
#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);
			add(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);//-horizontal double count
			add(duh,val[i]);
			val[jj]+=val[i];
			jj++;
		}
		add(ans,sz[cur]*(n-sz[cur])%mod);//advance
	}
	for(int i=l[id]; i<=r[id] ;i++) val[i]++;
	ll duh=0;
	ll tot=0;
	//cout << id << ": ";
	for(int i=l[id]; i<=r[id] ;i++){
		add(ans,duh*(sz[id]-duh)%mod);//-horizontal double count
		tot+=val[i]*duh;
		add(duh,val[i]);
		//cout << val[i] << ' ';
	}
	//cout << endl;
	//cout << "gain " << id << ": " << tot << endl;
}
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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5116 KB Output is correct
6 Correct 6 ms 5112 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 7 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 6 ms 5112 KB Output is correct
11 Correct 6 ms 5112 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 5084 KB Output is correct
3 Correct 7 ms 5240 KB Output is correct
4 Correct 7 ms 5240 KB Output is correct
5 Correct 7 ms 5240 KB Output is correct
6 Correct 7 ms 5240 KB Output is correct
7 Correct 7 ms 5240 KB Output is correct
8 Correct 8 ms 5112 KB Output is correct
9 Correct 7 ms 5212 KB Output is correct
10 Correct 8 ms 5244 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6136 KB Output is correct
2 Correct 16 ms 6236 KB Output is correct
3 Correct 30 ms 7824 KB Output is correct
4 Correct 30 ms 7800 KB Output is correct
5 Incorrect 54 ms 10360 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6652 KB Output is correct
2 Correct 20 ms 6520 KB Output is correct
3 Correct 41 ms 8696 KB Output is correct
4 Correct 35 ms 8500 KB Output is correct
5 Incorrect 68 ms 12284 KB Output isn't correct
6 Halted 0 ms 0 KB -