oj.uz

Submission #118667

# Submission time Handle Problem Language Result Execution time Memory
118667 2019-06-19T10:39:40 Z roseanne_pcy Ideal city (IOI12_city) C++14
100 / 100
 358 ms 31608 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 11648 KB Output is correct
2 Correct 13 ms 11776 KB Output is correct
3 Correct 12 ms 11648 KB Output is correct
4 Correct 12 ms 11648 KB Output is correct
5 Correct 12 ms 11648 KB Output is correct
6 Correct 12 ms 11776 KB Output is correct
7 Correct 12 ms 11648 KB Output is correct
8 Correct 12 ms 11648 KB Output is correct
9 Correct 11 ms 11648 KB Output is correct
10 Correct 11 ms 11748 KB Output is correct
11 Correct 11 ms 11648 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11904 KB Output is correct
2 Correct 13 ms 11904 KB Output is correct
3 Correct 13 ms 12032 KB Output is correct
4 Correct 13 ms 11904 KB Output is correct
5 Correct 13 ms 12032 KB Output is correct
6 Correct 13 ms 12032 KB Output is correct
7 Correct 14 ms 12028 KB Output is correct
8 Correct 14 ms 12032 KB Output is correct
9 Correct 13 ms 11904 KB Output is correct
10 Correct 14 ms 12004 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 14048 KB Output is correct
2 Correct 40 ms 14328 KB Output is correct
3 Correct 102 ms 17532 KB Output is correct
4 Correct 94 ms 17528 KB Output is correct
5 Correct 237 ms 23672 KB Output is correct
6 Correct 243 ms 23544 KB Output is correct
7 Correct 228 ms 23928 KB Output is correct
8 Correct 264 ms 23672 KB Output is correct
9 Correct 240 ms 23296 KB Output is correct
10 Correct 271 ms 31608 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 15352 KB Output is correct
2 Correct 49 ms 14968 KB Output is correct
3 Correct 137 ms 20368 KB Output is correct
4 Correct 121 ms 19576 KB Output is correct
5 Correct 325 ms 29048 KB Output is correct
6 Correct 269 ms 25796 KB Output is correct
7 Correct 358 ms 29560 KB Output is correct
8 Correct 300 ms 25976 KB Output is correct
9 Correct 271 ms 24860 KB Output is correct
10 Correct 265 ms 24804 KB Output is correct