Submission #401435

#	Time	Username	Problem	Language	Result	Execution time	Memory
401435		Jasiekstrz	Ideal city (IOI12_city)	C++17	23 / 100	77 ms	12212 KiB

city

/*
  w1  |  i
 ----------
 ?(p) |  w2
*/
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int NN=1e5;
const int MOD=1e9;
pair<int,int> t[NN+10];
map<pair<int,int>,int> id;
long long ans[NN+10];
long long siz[NN+10];
pair<long long,long long> dans[NN+10];
void set_siz(int l,int r,long long c)
{
	for(int i=l;i<=r;i++)
		siz[i]=c;
	return;
}
void add_ans(int l,int r,long long a,long long d) // a - value in r+1
{
	dans[r].fi+=a+d;
	dans[r].se+=d;
	dans[l-1].fi-=(a+d*(r-l+2))%MOD;
	dans[l-1].se-=d;
	return;
}
void recalc(int l,int r)
{
	long long c=0,d=0;
	for(int i=r;i>=l;i--,c+=d)
	{
		c+=dans[i].fi;
		d+=dans[i].se;
		c%=MOD;
		d%=MOD;
		ans[i]=(ans[i]+c)%MOD;
	}
	return;
}
int DistanceSum(int N,int *X,int *Y)
{
	int n=N;
	for(int i=0;i<n;i++)
		t[i+1]={X[i],Y[i]};
	sort(t+1,t+n+1);
	int bg=1;
	long long w=0;
	for(int i=1;i<=n;i++)
	{
		id[t[i]]=i;
		if(i>1 && (t[i].fi!=t[i-1].fi || t[i].se!=t[i-1].se+1))
		{
			recalc(bg,i-1);
			set_siz(bg,i-1,siz[i-1]);
			bg=i;
		}
		int w1=id[make_pair(t[i].fi-1,t[i].se)];
		int w2=i-1;
		int p=w1-1;
		if(w1==0 && bg==i) // no w1 nor w2
		{
			ans[i]=0;
			siz[i]=1;
		}
		else if(w1==0) // no w1
		{
			ans[i]=(ans[w2]+siz[w2])%MOD;
			siz[i]=siz[w2]+1;
			add_ans(bg,i-1,0,1);
		}
		else if(bg==i) // no w2
		{
			ans[i]=(ans[w1]+siz[w1])%MOD;
			siz[i]=siz[w1]+1;
		}
		else if(w1==1 || t[w1-1].fi!=t[w1].fi || t[w1-1].se!=t[w1].se-1) // no ?
		{
			ans[i]=(ans[w1]+ans[w2]+siz[w1]+siz[w2])%MOD;
			siz[i]=siz[w1]+siz[w2]+1;
			w+=(ans[w1]+siz[w1])*siz[w2]+(ans[w2]+siz[w2])*siz[w1];
			w%=MOD;
			add_ans(bg,i-1,ans[w1]+siz[w1],siz[w1]+1);
		}
		else // with ?
		{
			ans[i]=(ans[w1]+ans[w2]-ans[p]-siz[p]+siz[w2])%MOD;
			siz[i]=siz[w2]+1;
			add_ans(bg,i-1,0,1);
		}
		w=(w+ans[i])%MOD;
		//cerr<<t[i].fi<<" "<<t[i].se<<": "<<w<<"\n";
	}
	//recalc(bg,n);
	//for(int i=1;i<=n;i++)
	//	cerr<<t[i].fi<<" "<<t[i].se<<": "<<ans[i]<<" "<<siz[i]<<"\n";
	return (w+MOD)%MOD;
}

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