Submission #148080

#	Time	Username	Problem	Language	Result	Execution time	Memory
148080		WhipppedCream	Ideal city (IOI12_city)	C++17	100 / 100	347 ms	31608 KiB

city

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
 
const int maxn = 1e5+5;
 
const int md = 1e9;
 
void add(int &a, int b)
{
	a += b;
	if(a>= md) a -= md;
}
 
void sub(int &a, int b)
{
	a -= b;
	if(a< 0) a += md;
}
 
int mul(int a, int b)
{
	return (1LL*a*b)%md;
}
 
struct node
{
	int x, y1, y2;
	vector<int> num, dist;
	node(){}
	node(int _x, int _y1, int _y2)
	{
		x = _x; y1 = _y1; y2 = _y2;
	}
};
 
int xmin, ymin;
int xmax, ymax;
 
vector<int> buck[maxn];
node meg[maxn];
 
map< ii, int> mp;
 
vector<int> adj[maxn];
 
int cnt[maxn];
 
int findsum(int x)
{
	if(x%2 == 0) return mul(x, mul(x/2, x+1));
	return mul(x, mul(x, (x+1)/2));		
}
 
 
int ezreal = 0;
 
int lim;
int chote[maxn];
int summ[maxn];
int lalt[maxn];
int ralt[maxn];
 
int sum(int *ft, int x)
{
	x++;
	int res = 0;
	for(; x; x -= x&(-x)) add(res, ft[x]);
	return res;
}
 
int ask(int *ft, int a, int b)
{
	if(a> b) return 0;
	int res = sum(ft, b);
	sub(res, sum(ft, a-1));
	return res;
}
 
void update(int *ft, int x, int dx)
{
	x++;
	for(; x<= lim; x += x&(-x)) add(ft[x], dx);
}
 
void solve(int u, int p)
{
	for(auto v : adj[u])
	{
		if(v == p) continue;
		solve(v, u);
	}
	// printf("HERE %d\n", u);
	int len = meg[u].y2-meg[u].y1+1;
	meg[u].num.assign(len, 1);
	meg[u].dist.assign(len, 0);
	vector<int> &num = meg[u].num;
	vector<int> &dist = meg[u].dist;
	int y1 = meg[u].y1, y2 = meg[u].y2;
	lim = len;
	int sumdist = 0;
	for(int i = 0; i< len; i++)
	{
		update(summ, i, num[i]);
		update(lalt, i, i);
		update(ralt, i, len-1-i);
	}
	for(auto v : adj[u])
	{
		if(v == p) continue;
		// printf("it'ing through %d\n", v);
		int yy1 = meg[v].y1, yy2 = meg[v].y2;
		vector<int> &nump = meg[v].num;
		vector<int> &distp = meg[v].dist;
		for(int y = yy1; y<= yy2; y++)
		{
			int thiscnt = nump[y-yy1];
			int thisdist = distp[y-yy1];
			add(ezreal, mul(thiscnt, sumdist));
			add(ezreal, mul(thisdist, ask(summ, 0, len-1)));
			if(y1< y && y< y2)
			{
				int s = y-y1;
				add(ezreal, mul(thiscnt, ask(lalt, s, len-1)));
				sub(ezreal, mul(thiscnt, mul(s-1, ask(summ, s, len-1))));
				add(ezreal, mul(thiscnt, ask(ralt, 0, s-1)));
				sub(ezreal, mul(thiscnt, mul(len-1-s-1, ask(summ, 0, s-1))));
			}
			else if(y<= y1)
			{
				add(ezreal, mul(thiscnt, ask(lalt, 0, len-1)));
				add(ezreal, mul(thiscnt, mul(y1-y+1, ask(summ, 0, len-1))));
			}
			else
			{
				add(ezreal, mul(thiscnt, ask(ralt, 0, len-1)));
				add(ezreal, mul(thiscnt, mul(y-y2+1, ask(summ, 0, len-1))));
			}
		// printf("ezreal = %d\n", ezreal);
		}
		for(int y = yy1; y<= yy2; y++)
		{
			int can;
			if(y1<= y && y<= y2) can = y;
			else if(y< y1) can = y1;
			else can = y2;
			add(num[can-y1], nump[y-yy1]);
			update(summ, can-y1, nump[y-yy1]);
			update(lalt, can-y1, mul(can-y1, nump[y-yy1]));
			update(ralt, can-y1, mul(len-1-can+y1, nump[y-yy1]));
			add(dist[can-y1], distp[y-yy1]); add(sumdist, distp[y-yy1]);
			add(dist[can-y1], mul(nump[y-yy1], abs(can-y)+1)); add(sumdist, mul(nump[y-yy1], abs(can-y)+1));
		}
		// for(int i = 0; i< len; i++) printf("%d ", dist[i]);
		// printf("\n");
	}
	// for(int i = 0; i< len; i++) add(ezreal, dist[i]);
	add(ezreal, findsum(len));
	sub(ezreal, chote[len]);
	for(int i = 1; i<= len; i++) lalt[i] = summ[i] = ralt[i] = 0;
	// printf("for %d\n", u);
	// printf("dist: ");
	// for(int i = 0; i< len; i++) printf("%d ", dist[i]);
	// printf("\ncnt: ");
	// for(int i = 0; i< len; i++) printf("%d ", num[i]);
	// printf("\n");
	// printf("ezreal is %d\n", ezreal);
	// printf("\n\n");
}
int DistanceSum(int N, int *X, int *Y)
{
	xmin = ymin = 1e9;
	for(int i = 0; i< N; i++) xmin = min(xmin, X[i]), xmax = max(xmax, X[i]);
	for(int i = 0; i< N; i++) ymin = min(ymin, Y[i]), ymax = max(ymax, Y[i]);
	for(int i = 0; i< N; i++)
	{
		X[i] -= xmin; Y[i] -= ymin;
		buck[X[i]].pb(Y[i]);
	}
	int n = 0;
	for(int i = 0; i< N; i++)
	{
		sort(buck[i].begin(), buck[i].end());
		for(int j = 0; j< (int) buck[i].size(); j++)
		{
			int y = buck[i][j];
			if(j == 0)
			{
				n++;
				meg[n] = node(i, y, y);
			} 
			else if(meg[n].y2+1 != y)
			{
				n++; meg[n] = node(i, y, y);
			}
			else
			{
				meg[n].y2++;
			}
			mp[ii(i, y)] = n;
		}
	}
	for(int i = 0; i< N; i++)
	{
		int x = X[i], y = Y[i];
		int u = mp[ii(x, y)];
		int v1 = mp[ii(x+1, y)];
		int v2 = mp[ii(x-1, y)];
		if(v1)
		{
			adj[u].pb(v1); adj[v1].pb(u);
		}
		if(v2)
		{
			adj[u].pb(v2); adj[v2].pb(u);
		}
	}
	for(int i = 1; i<= n; i++) 
	{
		sort(adj[i].begin(), adj[i].end());
		adj[i].resize(unique(adj[i].begin(), adj[i].end())-adj[i].begin());
	}
	for(int i = 1; i<= 1e5; i++)
	{
		add(chote[i], chote[i-1]);
		add(chote[i], mul(i, i));
	}
	solve(1, 0);
	return ezreal;
}

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