Submission #401601

#	Time	Username	Problem	Language	Result	Execution time	Memory
401601		Jasiekstrz	Ideal city (IOI12_city)	C++17	100 / 100	55 ms	17112 KiB

city

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int NN=1e5;
const int MOD=1e9;
struct Node
{
	long long id;
	long long l,r;
	long long x;
};
pair<long long,long long> t[NN+10];
vector<Node> tab;
vector<int> e[NN+10];
vector<long long> w[NN+10];
vector<long long> siz[NN+10];
void mknode(int l,int r)
{
	//cerr<<"Node"<<tab.size()<<": x="<<t[l].fi<<" l="<<t[l].se<<" r="<<t[r].se<<"\n";
	w[tab.size()].resize(r-l+1);
	siz[tab.size()].resize(r-l+1);
	tab.push_back({tab.size(),t[l].se,t[r].se,t[l].fi});
	return;
}
long long merge(int x,int y) // merge y to x
{
	//cerr<<"merge Node"<<y<<" to Node"<<x<<": ";
	long long ans=0;
	int bi=max(0LL,tab[y].l-tab[x].l),bj=max(0LL,tab[x].l-tab[y].l);
	int ei=bi+min(w[x].size()-bi,w[y].size()-bj),ej=bj+min(w[x].size()-bi,w[y].size()-bj);
	//cerr<<"bi="<<bi<<" ei="<<ei<<" bj="<<bj<<" ej="<<ej<<" ";
	for(int i=0;i<bj;i++)
	{
		w[y][i+1]=(w[y][i+1]+siz[y][i]+w[y][i])%MOD;
		siz[y][i+1]=(siz[y][i+1]+siz[y][i])%MOD;
	}
	for(int i=w[y].size()-1;i>=ej;i--)
	{
		w[y][i-1]=(w[y][i-1]+siz[y][i]+w[y][i])%MOD;
		siz[y][i-1]=(siz[y][i-1]+siz[y][i])%MOD;
	}
	// whole y is in x
	long long p=0,s=0,ps=0,ss=0;
	for(int i=0;i<bi;i++)
	{
		p=(p+ps+w[x][i])%MOD;
		ps=(ps+siz[x][i])%MOD;
	}
	for(int i=w[x].size()-1;i>=ei;i--)
	{
		s=(s+ss+w[x][i])%MOD;
		ss=(ss+siz[x][i])%MOD;
	}
	for(int i=bi,j=bj;i<ei && j<ej;i++,j++)
	{
		p=(p+ps+w[x][i])%MOD;
		ps=(ps+siz[x][i])%MOD;
		ans=(ans+p*siz[y][j]+w[y][j]*ps+ps*siz[y][j])%MOD;
	}
	for(int i=ei-1,j=ej-1;i>=bi && j>=bj;i--,j--)
	{
		s=(s+ss)%MOD;
		ans=(ans+s*siz[y][j]+w[y][j]*ss+ss*siz[y][j])%MOD;
		s=(s+w[x][i])%MOD;
		ss=(ss+siz[x][i])%MOD;
	}
	for(int i=bi,j=bj;i<ei && j<ej;i++,j++)
	{
		siz[x][i]=(siz[x][i]+siz[y][j])%MOD;
		w[x][i]=(w[x][i]+w[y][j]+siz[y][j])%MOD;
	}
	//for(int i=0;i<w[x].size();i++)
	//	cerr<<"ww["<<i<<"]="<<w[x][i]<<" ss["<<i<<"]="<<siz[x][i]<<" ";
	//cerr<<"ans="<<ans<<"\n";
	return ans;
}
long long dfs(int x,int p)
{
	long long ans=0;
	long long tmp=0;
	for(int i=tab[x].l;i<=tab[x].r;i++)
	{
		tmp=(tmp+i-tab[x].l)%MOD;
		ans=(ans+tmp)%MOD;
	}
	fill(w[x].begin(),w[x].end(),0);
	fill(siz[x].begin(),siz[x].end(),1);
	for(auto v:e[x])
	{
		if(v==p)
			continue;
		ans+=dfs(v,x);
		ans+=merge(x,v);
		ans%=MOD;
	}
	return ans;
}
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;
	for(int i=1;i<=n;i++)
	{
		if(i!=1 && (t[i-1].fi!=t[i].fi || t[i-1].se+1!=t[i].se))
		{
			mknode(bg,i-1);
			bg=i;
		}
	}
	mknode(bg,n);
	int m=tab.size();
	for(int i=0,j=0;i<m;i++)
	{
		while(j<m && tab[j].x<tab[i].x && (tab[j].x<tab[i].x-1 || tab[j].r<tab[i].l))
			j++;
		while(j<m && tab[j].x==tab[i].x-1 && tab[j].l<=tab[i].r)
		{
			//cerr<<"link Node"<<i<<" Node"<<j<<"\n";
			e[i].push_back(j);
			e[j].push_back(i);
			j++;
		}
		if(j>0)
			j--;
		//cerr<<"after "<<i<<" "<<j<<"\n";
	}
	long long ans=dfs(0,-1);
	return (ans+MOD)%MOD;
}

Compilation message (stderr)

city.cpp: In function 'void mknode(int, int)':
city.cpp:23:25: warning: narrowing conversion of 'tab.std::vector<Node>::size()' from 'std::vector<Node>::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   23 |  tab.push_back({tab.size(),t[l].se,t[r].se,t[l].fi});
      |                 ~~~~~~~~^~

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