Submission #68847

#	Time	Username	Problem	Language	Result	Execution time	Memory
68847		Crown	Ideal city (IOI12_city)	C++14	0 / 100	81 ms	18812 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;
}

int mul(int a, int b)
{
	return (1LL*a*b)%md;
}

struct node
{
	int x, y1, y2;
	vector<int> res, 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 dim;
int stL[4*maxn];
int stR[4*maxn];
int lzL[4*maxn];
int lzR[4*maxn];
void build(int *st, int *lz, int p = 1, int L = 0, int R = dim-1)
{
	st[p] = 0; lz[p] = 0;
	if(L == R)
	{
		return;
	}
	build(st, lz, 2*p, L, (L+R)/2);
	build(st, lz, 2*p+1, (L+R)/2+1, R);
}

int ask(int *st, int *lz, int i, int j, int p = 1, int L = 0, int R = dim-1)
{
	if(i> R || j< L) return 0;
	if(i<= L && R<= j) return st[p];
	int M = (L+R)/2;
	if(lz[p])
	{
		add(st[2*p], mul(M-L+1, lz[p]));
		add(st[2*p+1], mul(R-M, lz[p]));
		add(lz[2*p], lz[p]);
		add(lz[2*p+1], lz[p]);
		lz[p] = 0;
	}
	int x = ask(st, lz, i, j, 2*p, L, (L+R)/2);
	int y = ask(st, lz, i, j, 2*p+1, (L+R)/2+1, R);
	add(x, y);
	return x;
}

void update(int *st, int *lz, int i, int j, int dx, int p = 1, int L = 0, int R = dim-1)
{
	if(i> R || j< L) return;
	if(i<= L && R<= j)
	{
		// printf("updated at %d (%d %d)\n", p, L, R);
		add(st[p], mul(R-L+1, dx));
		add(lz[p], dx);
		return;
	}
	int M = (L+R)/2;
	if(lz[p])
	{
		add(st[2*p], mul(M-L+1, lz[p]));
		add(st[2*p+1], mul(R-M, lz[p]));
		add(lz[2*p], lz[p]);
		add(lz[2*p+1], lz[p]);
		lz[p] = 0;
	}
	update(st, lz, i, j, dx, 2*p, L, (L+R)/2); update(st, lz, i, j, dx, 2*p+1, (L+R)/2+1, R);
	st[p] = st[2*p];
	add(st[p], st[2*p+1]);
}

int findsum(int x)
{
	if(x%2 == 0) return mul(x/2, x+1);
	return mul(x, (x+1)/2);		
}

int pong = 0;

void solve(int u, int p)
{
	for(auto v : adj[u])
	{
		if(v == p) continue;
		solve(v, u);
	}
	int len = meg[u].y2-meg[u].y1+1;
	cnt[u] = len;
	meg[u].res.assign(len, 0);
	meg[u].num.assign(len, 1);
	meg[u].dist.assign(len, 0);
	dim = len; build(stL, lzL); build(stR, lzR);
	for(int i = 0; i< len; i++)
	{
		meg[u].res[i] = findsum(i);
		add(meg[u].res[i], findsum(len-1-i));
	}
	// printf("now %d\n", u);
	for(auto v : adj[u])
	{
		if(v == p) continue;
		printf("it'ing over %d\n", v);
		for(int y = meg[v].y1; y<= meg[v].y2; y++)
		{
			int cnt = meg[v].num[y-meg[v].y1];
			int dist = meg[v].dist[y-meg[v].y1];
			int can;
			if(meg[u].y1<= y && y<= meg[u].y2)
			{
				can = y;
				add(dist, cnt);
			}
			else if(y< meg[u].y1)
			{
				can = meg[u].y1;
				add(dist, mul(meg[u].y1-y+1, cnt));
			}
			else
			{
				can = meg[u].y2;
				add(dist, mul(y-meg[u].y2+1, cnt));
			}
			printf("added %d*%d\n", dist, meg[u].res[can-meg[u].y1]+ask(stL, lzL, 0, can-meg[u].y1)+ask(stR, lzR, can-meg[u].y1, meg[u].y2-meg[u].y1));
			add(pong, mul(dist, meg[u].res[can-meg[u].y1]));
			add(pong, mul(dist, ask(stL, lzL, 0, can-meg[u].y1)));
			add(pong, mul(dist, ask(stR, lzR, can-meg[u].y1, meg[u].y2-meg[u].y1)));
		}
		for(int y = meg[v].y1; y<= meg[v].y2; y++)
		{
			if(meg[u].y1<= y && y<= meg[u].y2)
			{
				add(meg[u].res[y-meg[u].y1], meg[v].res[y-meg[v].y1]);
				add(meg[u].res[y-meg[u].y1], cnt[v]);
			}
		}
		int temp = meg[v].res.back(); add(temp, 2*cnt[v]);
		update(stL, lzL, meg[v].y2+1-meg[u].y1, meg[v].y2+1-meg[u].y1, temp);
		// printf("temp is %d at %d\n", temp, meg[v].y2+1-meg[u].y1);
		update(stL, lzL, meg[v].y2+2-meg[u].y1, dim-1, cnt[v]);
		temp = meg[v].res[0]; add(temp, 2*cnt[v]);
		update(stR, lzR, meg[v].y1-1-meg[u].y1, meg[v].y1-1-meg[u].y1, temp);
		update(stR, lzR, 0, meg[v].y1-2-meg[u].y1, cnt[v]);
		cnt[u] += cnt[v];
		for(int y = meg[v].y1; y<= meg[v].y2; y++)
		{
			if(meg[u].y1<= y && y<= meg[u].y2)
			{
				add(meg[u].num[y-meg[u].y1], meg[v].num[y-meg[v].y1]);
				add(meg[u].dist[y-meg[u].y1], meg[v].dist[y-meg[v].y1]);
				add(meg[u].dist[y-meg[u].y1], meg[v].num[y-meg[v].y1]);
			}
			else if(y< meg[u].y1)
			{	
				add(meg[u].num[0], meg[v].num[y-meg[v].y1]);
				add(meg[u].dist[0], meg[v].dist[y-meg[v].y1]);
				add(meg[u].dist[0], mul(meg[u].y1-y+1, meg[v].num[y-meg[v].y1]));
			}
			else 
			{
				add(meg[u].num.back(), meg[v].num[y-meg[v].y1]);
				add(meg[u].dist.back(), meg[v].dist[y-meg[v].y1]);
				add(meg[u].dist.back(), mul(y-meg[u].y2+1, meg[v].num[y-meg[v].y1]));
			}
		}

	printf("res: ");
	for(int i = 0; i< len; i++) printf("%d ", meg[u].res[i]+ask(stL, lzL, 0, i)+ask(stR, lzR, i, dim-1));
	printf("\n");
	}
	for(int i = 0; i< len; i++)
	{
		add(meg[u].res[i], ask(stL, lzL, 0, i));
		add(meg[u].res[i], ask(stR, lzR, i, dim-1));
	}
	printf("meg[%d]:\n", u);
	printf("res: ");
	for(int i = 0; i< len; i++) printf("%d ", meg[u].res[i]);
	printf("\n");
	printf("dist: ");
	for(int i = 0; i< len; i++) printf("%d ", meg[u].dist[i]);
	printf("\n");
	printf("num: ");
	for(int i = 0; i< len; i++) printf("%d ", meg[u].num[i]);
	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());
	}
	solve(1, 0);
	return pong;
}

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