oj.uz

Submission #578694

# Submission time Handle Problem Language Result Execution time Memory
578694 2022-06-17T15:56:21 Z WongChun1234 Ideal city (IOI12_city) C++14
100 / 100
 578 ms 47496 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100050;
const ll MOD=1000000000;
const bool DEBUG=0;
int n,cx,cnt[N],grpcnt,ingrp[N];
ll ans,dist[N];
vector<pair<int,int>> curr,grps[N];
pair<int,int> coord[N];
map<int,vector<pair<int,int>>> mp;
map<pair<int,int>,int> hv;
ll f(ll num){
	return (1+num)*num/2%MOD;
}
void dfs(int nde,int par,pair<int,int> connection,bool up){
	vector<array<ll,2>> frntsum,frntcnt,bcksum,bckcnt;
	int cx=coord[grps[nde][0].second-1].first,cy=INT_MAX,cz=grps[nde].size();
	ll csum=0,ccnt=0,lzsum=0,lzcnt=0,dup=0;
	frntsum.resize(cz); frntcnt.resize(cz); bcksum.resize(cz); bckcnt.resize(cz);
	if (DEBUG) cerr<<"dfs"<<cx<<"::"<<connection.first<<","<<connection.second<<"\n";
	for (auto i:grps[nde]){
		if (!hv[{cx+1,i.first}]) continue;
		if (ingrp[hv[{cx+1,i.first}]]==par) continue;
		cy=min(cy,i.first);
		if (hv[{cx+1,i.first+1}]&&i!=grps[nde].back()) continue;
		dfs(ingrp[hv[{cx+1,i.first}]],nde,{cy,i.first},0);
		cy=INT_MAX;
	}
	cy=INT_MAX;
	for (auto i:grps[nde]){
		if (!hv[{cx-1,i.first}]) continue;
		if (ingrp[hv[{cx-1,i.first}]]==par) continue;
		cy=min(cy,i.first);
		if (hv[{cx-1,i.first+1}]&&i!=grps[nde].back()) continue;
		dfs(ingrp[hv[{cx-1,i.first}]],nde,{cy,i.first},1);
		cy=INT_MAX;
	}
	// down down, up up
	if (DEBUG) cerr<<"PROCESSING"<<ans<<"\n";
	for (auto i:grps[nde]){
		if (DEBUG) cerr<<cx<<","<<i.first<<"\n";
		csum+=ccnt;
		csum%=MOD;
		lzsum+=lzcnt;
		lzsum%=MOD;
		if (DEBUG) cerr<<csum<<","<<ccnt<<";"<<lzsum<<","<<lzcnt<<":"<<ans<<"\n";
		if (hv[{cx-1,i.first}]&&ingrp[hv[{cx-1,i.first}]]!=par){
			lzcnt+=cnt[hv[{cx-1,i.first}]];
			lzsum+=dist[hv[{cx-1,i.first}]]+cnt[hv[{cx-1,i.first}]];
			lzcnt%=MOD; lzsum%=MOD;
			ans+=ccnt*(dist[hv[{cx-1,i.first}]]+cnt[hv[{cx-1,i.first}]]);
			ans+=csum*cnt[hv[{cx-1,i.first}]];
			ans%=MOD;
			if (DEBUG) cerr<<ans<<"::\n";
		}else{
			csum+=lzsum;
			csum%=MOD;
			ccnt+=lzcnt;
			ccnt%=MOD;
			lzsum=lzcnt=0;
		}
	}
	csum=lzsum=ccnt=lzcnt=0;
	for (auto i:grps[nde]){
		if (DEBUG) cerr<<cx<<","<<i.first<<"\n";
		csum+=ccnt;
		csum%=MOD;
		lzsum+=lzcnt;
		lzsum%=MOD;
		if (DEBUG) cerr<<csum<<","<<ccnt<<";"<<lzsum<<","<<lzcnt<<":"<<ans<<"\n";
		if (hv[{cx+1,i.first}]&&ingrp[hv[{cx+1,i.first}]]!=par){
			lzcnt+=cnt[hv[{cx+1,i.first}]];
			lzsum+=dist[hv[{cx+1,i.first}]]+cnt[hv[{cx+1,i.first}]];
			lzcnt%=MOD; lzsum%=MOD;
			ans+=ccnt*(dist[hv[{cx+1,i.first}]]+cnt[hv[{cx+1,i.first}]]);
			ans+=csum*cnt[hv[{cx+1,i.first}]];
			ans%=MOD;
			if (DEBUG) cerr<<ans<<"::\n";
		}else{
			csum+=lzsum;
			csum%=MOD;
			ccnt+=lzcnt;
			ccnt%=MOD;
			lzsum=lzcnt=0;
		}
	}
	// down to up
	for (int i=0;i<cz;i++){
		if (i){
			frntsum[i][0]=(frntsum[i-1][0]+frntcnt[i-1][0])%MOD;
			frntcnt[i][0]=frntcnt[i-1][0];
			frntsum[i][1]=(frntsum[i-1][1]+frntcnt[i-1][1])%MOD;
			frntcnt[i][1]=frntcnt[i-1][1];
		}
		dup+=ccnt;
		ccnt+=i+1;
		ccnt%=MOD; dup%=MOD;
		if (hv[{cx-1,grps[nde][i].first}]&&ingrp[hv[{cx-1,grps[nde][i].first}]]!=par){
			frntcnt[i][0]+=cnt[hv[{cx-1,grps[nde][i].first}]];
			frntsum[i][0]+=dist[hv[{cx-1,grps[nde][i].first}]]+cnt[hv[{cx-1,grps[nde][i].first}]];
			frntsum[i][0]%=MOD;
		}
		if (hv[{cx+1,grps[nde][i].first}]&&ingrp[hv[{cx+1,grps[nde][i].first}]]!=par){
			frntcnt[i][1]+=cnt[hv[{cx+1,grps[nde][i].first}]];
			frntsum[i][1]+=dist[hv[{cx+1,grps[nde][i].first}]]+cnt[hv[{cx+1,grps[nde][i].first}]];
			frntsum[i][1]%=MOD;
		}
	}
	for (int i=cz-1;~i;i--){
		if (i!=cz-1){
			bcksum[i][0]=(bcksum[i+1][0]+bckcnt[i+1][0])%MOD;
			bckcnt[i][0]=bckcnt[i+1][0];
			bcksum[i][1]=(bcksum[i+1][1]+bckcnt[i+1][1])%MOD;
			bckcnt[i][1]=bckcnt[i+1][1];
		}
		if (hv[{cx-1,grps[nde][i].first}]&&ingrp[hv[{cx-1,grps[nde][i].first}]]!=par){
			bckcnt[i][0]+=cnt[hv[{cx-1,grps[nde][i].first}]];
			bcksum[i][0]+=dist[hv[{cx-1,grps[nde][i].first}]]+cnt[hv[{cx-1,grps[nde][i].first}]];
			bcksum[i][0]%=MOD;
		}
		if (hv[{cx+1,grps[nde][i].first}]&&ingrp[hv[{cx+1,grps[nde][i].first}]]!=par){
			bckcnt[i][1]+=cnt[hv[{cx+1,grps[nde][i].first}]];
			bcksum[i][1]+=dist[hv[{cx+1,grps[nde][i].first}]]+cnt[hv[{cx+1,grps[nde][i].first}]];
			bcksum[i][1]%=MOD;
		}
	}
	if (DEBUG) for (int i=0;i<cz;i++) cerr<<frntsum[i][0]<<" "<<frntsum[i][1]<<" "<<frntcnt[i][0]<<" "<<frntcnt[i][1]<<"\n";
	for (int i=0;i<cz;i++){
		ans+=bcksum[i][0]+bcksum[i][1];
		ans%=MOD;
		if (i) ans+=frntsum[i-1][0]+frntsum[i-1][1]+frntcnt[i-1][0]+frntcnt[i-1][1];
		ans%=MOD;
		if (DEBUG) cerr<<cx<<","<<grps[nde][i].first<<":"<<ans<<"\n";
		if (!hv[{cx+1,grps[nde][i].first}]||ingrp[hv[{cx+1,grps[nde][i].first}]]==par) continue;
		ans+=(dist[hv[{cx+1,grps[nde][i].first}]]+cnt[hv[{cx+1,grps[nde][i].first}]])%MOD*bckcnt[i][0];
		ans%=MOD;
		ans+=bcksum[i][0]*cnt[hv[{cx+1,grps[nde][i].first}]];
		ans%=MOD;
		if (i){
			ans+=(dist[hv[{cx+1,grps[nde][i].first}]]+cnt[hv[{cx+1,grps[nde][i].first}]])%MOD*frntcnt[i-1][0];
			ans%=MOD;
			ans+=(frntsum[i-1][0]+frntcnt[i-1][0])*cnt[hv[{cx+1,grps[nde][i].first}]];
			ans%=MOD;
		}
		if (DEBUG) cerr<<cx<<","<<grps[nde][i].first<<":"<<ans<<"\n";
	}
	for (int i=0;i<cz;i++){
		if (up){
			cnt[hv[{cx,grps[nde][i].first}]]=cnt[hv[{cx-1,grps[nde][i].first}]]+1;
			dist[hv[{cx,grps[nde][i].first}]]=dist[hv[{cx-1,grps[nde][i].first}]]+cnt[hv[{cx-1,grps[nde][i].first}]];
			dist[hv[{cx,grps[nde][i].first}]]%=MOD;
		}else{
			cnt[hv[{cx,grps[nde][i].first}]]=cnt[hv[{cx+1,grps[nde][i].first}]]+1;
			dist[hv[{cx,grps[nde][i].first}]]=dist[hv[{cx+1,grps[nde][i].first}]]+cnt[hv[{cx+1,grps[nde][i].first}]];
			dist[hv[{cx,grps[nde][i].first}]]%=MOD;
		}
		if (grps[nde][i].first==connection.first){
			if (i){
				cnt[hv[{cx,grps[nde][i].first}]]+=frntcnt[i-1][0]+frntcnt[i-1][1]+i;
				dist[hv[{cx,grps[nde][i].first}]]+=frntsum[i-1][0]+frntsum[i-1][1]+frntcnt[i-1][0]+frntcnt[i-1][1]+f(i);
				dist[hv[{cx,grps[nde][i].first}]]%=MOD;
			}
		}
		if (grps[nde][i].first==connection.second){
			if (i<cz-1){
				cnt[hv[{cx,grps[nde][i].first}]]+=bckcnt[i+1][0]+bckcnt[i+1][1]+cz-i-1;
				dist[hv[{cx,grps[nde][i].first}]]+=bcksum[i+1][0]+bcksum[i+1][1]+bckcnt[i+1][0]+bckcnt[i+1][1]+f(cz-i-1);
				dist[hv[{cx,grps[nde][i].first}]]%=MOD;
			}
		}
		if (DEBUG) cerr<<cx<<":::"<<grps[nde][i].first<<":"<<cnt[hv[{cx,grps[nde][i].first}]]<<","<<dist[hv[{cx,grps[nde][i].first}]]<<"\n";
	}
	for (int i=0;i<cz;i++) ans+=f(i);
}
void addgrp(){
	grps[++grpcnt]=curr;
	for (auto i:curr) ingrp[i.second]=grpcnt;
	curr.clear();
}
int DistanceSum(int _N, int *x, int *y) {
	n=_N;
	for (int i=0;i<n;i++) coord[i]={x[i],y[i]};
	sort(coord,coord+n);
	for (int i=0;i<n;i++){
		hv[coord[i]]=i+1;
		mp[coord[i].first].push_back({coord[i].second,i+1});
	}
	for (auto i:mp){
		cx=i.first;
		curr.clear();
		for (auto j:i.second){
			if (curr.empty()||j.first==curr.back().first+1){
				curr.push_back(j);
			}else{
				addgrp();
				curr.push_back(j);
			}
		}
		if (curr.size()) addgrp();
	}
	dfs(1,1,{-1,-1},0);
	return ans;
}

/*
6
1 1
2 1
2 3
3 1
3 2
3 3
*/

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2804 KB Output is correct
2 Correct 5 ms 2812 KB Output is correct
3 Correct 7 ms 3036 KB Output is correct
4 Correct 7 ms 3028 KB Output is correct
5 Correct 9 ms 3104 KB Output is correct
6 Correct 8 ms 3028 KB Output is correct
7 Correct 8 ms 3156 KB Output is correct
8 Correct 9 ms 3028 KB Output is correct
9 Correct 9 ms 3072 KB Output is correct
10 Correct 9 ms 3064 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 6608 KB Output is correct
2 Correct 69 ms 6972 KB Output is correct
3 Correct 165 ms 12372 KB Output is correct
4 Correct 172 ms 12768 KB Output is correct
5 Correct 317 ms 21656 KB Output is correct
6 Correct 381 ms 22404 KB Output is correct
7 Correct 338 ms 22704 KB Output is correct
8 Correct 328 ms 21396 KB Output is correct
9 Correct 365 ms 23372 KB Output is correct
10 Correct 578 ms 47496 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 6564 KB Output is correct
2 Correct 85 ms 7236 KB Output is correct
3 Correct 194 ms 12100 KB Output is correct
4 Correct 189 ms 12036 KB Output is correct
5 Correct 437 ms 21264 KB Output is correct
6 Correct 381 ms 19620 KB Output is correct
7 Correct 434 ms 22636 KB Output is correct
8 Correct 396 ms 19644 KB Output is correct
9 Correct 373 ms 17144 KB Output is correct
10 Correct 404 ms 16892 KB Output is correct