Submission #280407

#	Time	Username	Problem	Language	Result	Execution time	Memory
280407		amiratou	Ideal city (IOI12_city)	C++14	32 / 100	142 ms	5624 KiB

city

#include <bits/stdc++.h> 
using namespace std;
#define fi first
#define se second
const int MOD = (int)(1e9);
const int INF = INT_MAX;
typedef pair<int,int> ii;
typedef long long ll;

map<ii,int> nodes;
int adj[100005][4],dist[100005],xs[]={0,0,-1,1},ys[]={1,-1,0,0},n,pos[100005];
ll fen[3][100005];
void update(int t,int idx,int val){
	for (int i = idx; i <= n; i+=(i&(-i)))
		fen[t][i]=(fen[t][i]+val)%MOD;
}
int get(int t,int idx){
	int h=0;
	for (int i = idx; i >= 1; i-=(i&(-i)))
		h=(h+fen[t][i])%MOD;
	return h;
}
int sum(int t,int a,int b){
	return (get(t,b)-get(t,a-1)+MOD)%MOD;
}

int DistanceSum(int N, int *X, int *Y) {
	n=N;
	ll ans=0;
	if(N<=2000){
		memset(adj,-1,sizeof adj);
		for (int i = 0; i < N; ++i)
			nodes[{X[i],Y[i]}]=i;
		for (int i = 0; i < N; ++i)
			for (int d = 0; d < 4; ++d)
				if(nodes.count({X[i]+xs[d],Y[i]+ys[d]}))
					adj[i][d]=nodes[{X[i]+xs[d],Y[i]+ys[d]}];
		for (int i = 0; i < N; ++i)
		{
			queue<int> q;
			for (int j = 0; j < N; ++j)dist[j]=INF;
			q.push(i);
			dist[i]=0;
			while(!q.empty()){
				int f=q.front();
				q.pop();
				for (int d = 0; d < 4; ++d)
					if(adj[f][d]!=-1 && dist[adj[f][d]]==INF){
						dist[adj[f][d]]=dist[f]+1,q.push(adj[f][d]);
						if(dist[adj[f][d]]>=MOD)dist[adj[f][d]]%=MOD;
					}
			}
			for (int j = i+1; j < N; ++j)
			{
				ans+=dist[j];
				if(ans>=MOD)ans%=MOD;
			}
		}	
	}
	else{
		vector<ii> vec(N),vecX(N);
		for (int i = 0; i < N; ++i){
			vec[i]={Y[i],i};
			vecX[i]={X[i],i};
		}
		sort(vec.begin(),vec.end());
		sort(vecX.begin(),vecX.end());
		for (int i = 1; i <= N; ++i){
			int k=vecX[i-1].se;
			pos[k]=i;
			update(0,i,1),update(1,i,(X[k]+Y[k])%MOD),update(2,i,(Y[k]-X[k]+MOD)%MOD);
		}
		for (int i = 1; i <= N; ++i)
		{
			int id=vec[i-1].se,y=vec[i-1].fi;
			update(0,pos[id],-1),update(1,pos[id],(MOD-(X[id]%MOD+Y[id]%MOD)%MOD)%MOD),update(2,pos[id],(X[id]-Y[id]+MOD)%MOD);
			ans=(ans+(sum(1,pos[id],n)-((sum(0,pos[id],n)*((X[id]+y)%MOD))%MOD) + MOD)%MOD)%MOD;
			ans=(ans+(sum(2,1,pos[id])+((sum(0,1,pos[id])*((X[id]-y)%MOD))%MOD))%MOD)%MOD;
		}
	}
	return (int)ans;

}

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