oj.uz

답안 #68876

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
68876 2018-08-18T20:53:06 Z Crown 이상적인 도시 (IOI12_city) C++14
100 / 100
 406 ms 32908 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 pong = 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(pong, mul(thiscnt, sumdist));
			add(pong, mul(thisdist, ask(summ, 0, len-1)));
			if(y1< y && y< y2)
			{
				int s = y-y1;
				add(pong, mul(thiscnt, ask(lalt, s, len-1)));
				sub(pong, mul(thiscnt, mul(s-1, ask(summ, s, len-1))));
				add(pong, mul(thiscnt, ask(ralt, 0, s-1)));
				sub(pong, mul(thiscnt, mul(len-1-s-1, ask(summ, 0, s-1))));
			}
			else if(y<= y1)
			{
				add(pong, mul(thiscnt, ask(lalt, 0, len-1)));
				add(pong, mul(thiscnt, mul(y1-y+1, ask(summ, 0, len-1))));
			}
			else
			{
				add(pong, mul(thiscnt, ask(ralt, 0, len-1)));
				add(pong, mul(thiscnt, mul(y-y2+1, ask(summ, 0, len-1))));
			}
		// printf("pong = %d\n", pong);
		}
		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(pong, dist[i]);
	add(pong, findsum(len));
	sub(pong, 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("pong is %d\n", pong);
	// 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 pong;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 11640 KB Output is correct
2 Correct 13 ms 11752 KB Output is correct
3 Correct 13 ms 11828 KB Output is correct
4 Correct 15 ms 11884 KB Output is correct
5 Correct 15 ms 11920 KB Output is correct
6 Correct 14 ms 11920 KB Output is correct
7 Correct 15 ms 11920 KB Output is correct
8 Correct 15 ms 11996 KB Output is correct
9 Correct 15 ms 12044 KB Output is correct
10 Correct 15 ms 12044 KB Output is correct
11 Correct 15 ms 12044 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 12216 KB Output is correct
2 Correct 15 ms 12216 KB Output is correct
3 Correct 14 ms 12268 KB Output is correct
4 Correct 17 ms 12268 KB Output is correct
5 Correct 16 ms 12396 KB Output is correct
6 Correct 15 ms 12396 KB Output is correct
7 Correct 17 ms 12396 KB Output is correct
8 Correct 16 ms 12396 KB Output is correct
9 Correct 17 ms 12396 KB Output is correct
10 Correct 14 ms 12396 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 14312 KB Output is correct
2 Correct 53 ms 14444 KB Output is correct
3 Correct 149 ms 17524 KB Output is correct
4 Correct 118 ms 17524 KB Output is correct
5 Correct 286 ms 23408 KB Output is correct
6 Correct 265 ms 23408 KB Output is correct
7 Correct 316 ms 23408 KB Output is correct
8 Correct 300 ms 23408 KB Output is correct
9 Correct 233 ms 23660 KB Output is correct
10 Correct 290 ms 32908 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 32908 KB Output is correct
2 Correct 53 ms 32908 KB Output is correct
3 Correct 167 ms 32908 KB Output is correct
4 Correct 174 ms 32908 KB Output is correct
5 Correct 387 ms 32908 KB Output is correct
6 Correct 339 ms 32908 KB Output is correct
7 Correct 406 ms 32908 KB Output is correct
8 Correct 367 ms 32908 KB Output is correct
9 Correct 301 ms 32908 KB Output is correct
10 Correct 340 ms 32908 KB Output is correct