Submission #280411

#	Time	Username	Problem	Language	Result	Execution time	Memory
280411		amiratou	Ideal city (IOI12_city)	C++14	55 / 100	152 ms	7544 KiB

city

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

map<ii,ll> nodes;
ll adj[100005][4],dist[100005],xs[]={0,0,-1,1},ys[]={1,-1,0,0},n,pos[100005];
ll fen[3][100005];
void update(ll t,ll idx,ll val){
	for (ll i = idx; i <= n; i+=(i&(-i)))
		fen[t][i]=(fen[t][i]+val)%MOD;
}
ll get(ll t,ll idx){
	ll h=0;
	for (ll i = idx; i >= 1; i-=(i&(-i)))
		h=(h+fen[t][i])%MOD;
	return h;
}
ll sum(ll t,ll a,ll 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 (ll i = 0; i < N; ++i)
			nodes[{X[i],Y[i]}]=i;
		for (ll i = 0; i < N; ++i)
			for (ll 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 (ll i = 0; i < N; ++i)
		{
			queue<ll> q;
			for (ll j = 0; j < N; ++j)dist[j]=INF;
			q.push(i);
			dist[i]=0;
			while(!q.empty()){
				ll f=q.front();
				q.pop();
				for (ll 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 (ll j = i+1; j < N; ++j)
			{
				ans+=dist[j];
				if(ans>=MOD)ans%=MOD;
			}
		}	
	}
	else{
		vector<ii> vec(N),vecX(N);
		for (ll 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 (ll i = 1; i <= N; ++i){
			ll k=vecX[i-1].se;
			pos[k]=i;
			update(0,i,1),update(1,i,((X[k])%MOD+(Y[k])%MOD)%MOD),update(2,i,(Y[k]-(X[k])%MOD+(MOD))%MOD);
		}
		for (ll i = 1; i <= N; ++i)
		{
			ll id=vec[i-1].se,y=(vec[i-1].fi%MOD);
			update(0,pos[id],-1),update(1,pos[id],(MOD-(X[id]%MOD+Y[id]%MOD)%MOD)%MOD),update(2,pos[id],((X[id])%MOD-(Y[id]%MOD)+MOD)%MOD);
			for (ll z = 0; z < 3; ++z)
				assert(sum(z,pos[id],pos[id])==0);
			ans=(ans+(sum(1,pos[id],n)-((sum(0,pos[id],n)*(((X[id])%MOD+y)%MOD))%MOD) + MOD)%MOD)%MOD;
			ans=(ans+(sum(2,1,pos[id])+((sum(0,1,pos[id])*(((X[id])%MOD-y+MOD)%MOD))%MOD))%MOD)%MOD;
		}
	}
	return (ll)ans;

}

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