Submission #121856

#	Time	Username	Problem	Language	Result	Execution time	Memory
121856		baluteshih	Ideal city (IOI12_city)	C++14	55 / 100	107 ms	7692 KiB

city

#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

ll dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},ans;
const ll MOD=1e9;
vector<ll> G[100005];
vector<pll> v;
bitset<100005> vis;
unordered_map<ll,ll> mp;

void DQ(ll l,ll r)
{
	if(l==r) return;
	ll m=l+r>>1,a,b,sum=0,rsum=0;
	DQ(l,m),DQ(m+1,r);
	queue<pll> q;
	for(a=l;a<=m;++a)
		sum=(sum+v[a].F+v[a].S)%MOD;
	for(a=l,b=m+1;a<=m&&b<=r;)
		if(v[a].S>=v[b].S)
			sum=(sum-v[a].F%MOD-v[a].S%MOD+MOD+MOD)%MOD,rsum=(rsum+v[a].F-v[a].S%MOD+MOD)%MOD,q.push(v[a++]);
		else
			ans=(ans+(v[b].F+v[b].S)*(m-a+1)+(v[b].F-v[b].S)*(a-l)-sum+MOD-rsum+MOD)%MOD,q.push(v[b++]);
	while(a<=m)
		q.push(v[a++]);
	while(b<=r)
		ans=(ans+(v[b].F+v[b].S)*(m-a+1)+(v[b].F-v[b].S)*(a-l)-sum+MOD-rsum+MOD)%MOD,q.push(v[b++]);
	for(int i=l;i<=r;++i)
		v[i]=q.front(),q.pop();	
}

int DistanceSum(int N, int *X, int *Y)
{
	if(N<=2000)
	{
		for(int i=0;i<N;++i)
			mp[(ll)X[i]<<31|Y[i]]=i;
		for(int i=0;i<N;++i)
			for(int j=0;j<4;++j)
			{
				auto p=mp.find(((ll)(X[i]+dx[j])<<31)|(Y[i]+dy[j]));
				if(p!=mp.end()) G[i].pb(p->S);
			}
		for(int i=0;i<N;++i)
		{
			int tp=0;
			queue<pii> q;
			q.push(MP(i,0)),vis.reset(),vis[i]=1;
			while(!q.empty())
			{
				auto tmp=q.front();
				q.pop(),ans=(ans+tmp.S)%MOD,vis[tmp.F]=1;
				for(int j:G[tmp.F])
					if(!vis[j]) q.push(MP(j,tmp.S+1)),vis[j]=1;
				++tp;
			}
		}
		ans/=2;
	}
	else
	{
		for(int i=0;i<N;++i)
			v.pb(MP((ll)X[i],(ll)Y[i]));
		sort(ALL(v)),DQ(0,N-1);
	}
	return ans;
}

Compilation message (stderr)

city.cpp: In function 'void DQ(ll, ll)':
city.cpp:26:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  ll m=l+r>>1,a,b,sum=0,rsum=0;
       ~^~

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