oj.uz

Submission #53285

# Submission time Handle Problem Language Result Execution time Memory
53285 2018-06-29T07:39:11 Z 윤교준(#1402) Adriatic (CEOI13_adriatic) C++11
100 / 100
 565 ms 105196 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
//#define rf(x) (x)=0;while(*p<48)im=*p=='-';while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);if(im)(x)=-(x);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define cb(x) (x)=(!(x))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define INFST (0x7f7f7f7f)
#define INFLLST (0x7f7f7f7f7f7f7f7fll)
using namespace std;
typedef long long ll;
typedef __int128_t lll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ld, ld> pdd;
typedef complex<ld> base;
const ld EPS = (ld)1e-7;
const ld PI = acos(0) * 2;
bool isZero(const ld& x) { return abs(x) <= EPS; }
int sign(const ld& x) { return isZero(x) ? 0 : (0 < x ? 1 : -1); }
ll gcd(ll a, ll b) { for(;b;a%=b,swap(a,b)){} return abs(a); }
pll operator + (const pll& a, const pll& b) { return pll(a.first+b.first, a.second+b.second); }
pll operator - (const pll& a, const pll& b) { return pll(a.first-b.first, a.second-b.second); }
pll operator * (const pll& a, const ll& b) { return pll(a.first*b, a.second*b); }
ll operator * (const pll& a, const pll& b) { return a.first*b.second - b.first*a.second; }
ll ccw(const pll& a, const pll& b, const pll& c) { return a*b + b*c + c*a; }
int rd(int s, int e) { return rand()%(e-s+1) + s; }
void fg(vector<int> G[], int a, int b) { G[a].pb(b); G[b].pb(a); }
void fg(vector<pii> G[], int a, int b, int c) { G[a].pb({b, c}); G[b].pb({a, c}); }

const int MAXN = 250005;
const int MAXX = 2505;

ll ddr[MAXX][MAXX];

int A[MAXX][MAXX], S[MAXX][MAXX];

int dmxx[MAXX], dmny[MAXX];
int Y[MAXN], X[MAXN];

ll Ans[MAXN];

int N;

void init() {
	for(int i = 0; i < MAXX; i++)
		fill(ddr[i], ddr[i]+MAXX, 0);
	for(int i = 0; i < MAXX; i++) {
		fill(A[i], A[i]+MAXX, 0);
		fill(S[i], S[i]+MAXX, 0);
	}
	fill(dmxx, dmxx+MAXX, 0);
	fill(dmny, dmny+MAXX, 0);
}

int f(int ys, int ye, int xs, int xe) {
	if(ys > ye || xs > xe) return 0;
	ys--; xs--;
	return S[ye][xe] - S[ys][xe] + S[ys][xs] - S[ye][xs];
}

ll g(int y, int x) {
	ll &ret = ddr[y][x];
	if(0 <= ret) return ret;
	if(!!A[y][x] == f(1, y, x, MAXX-1)) return (ret = 0);

	ret = INFLL;

	int a = dmxx[y+1], b = dmny[x-1];
	if(!a || x >= X[a]) a = 0;
	if(!b || y <= Y[b]) b = 0;

	//printf("%d %d : %d %d\n", y, x, a, b);

	if(a && b) {
		ll t = f(1, y, x, X[a]-1) + f(Y[b]+1, y, x, MAXX-1) - f(Y[b]+1, y, x, X[a]-1);
		if(A[y][x]) t--;
		t *= 2;

		if(f(1, Y[b], X[a], MAXX-1)) {
			t += g(Y[b], X[a]) + f(1, Y[b], X[a], MAXX-1);
			if(A[Y[b]][X[a]]) t += 2;
		}
		upmin(ret, t);
	}
	if(a) {
		ll t = f(1, y, x, X[a]-1) - !!A[y][x];
		t *= 2;

		if(f(1, y, X[a], MAXX-1)) {
			t += g(y, X[a]) + f(1, y, X[a], MAXX-1);
			if(A[y][X[a]]) t += 2;
		}
		upmin(ret, t);
	}
	if(b) {
		ll t = f(Y[b]+1, y, x, MAXX-1) - !!A[y][x];
		t *= 2;

		if(f(1, Y[b], x, MAXX-1)) {
			//printf("CHK %d %d : %d %d :: %lld\n", y, x, Y[b], x, g(Y[b], x));
			t += g(Y[b], x) + f(1, Y[b], x, MAXX-1);
			if(A[Y[b]][x]) t += 2;
		}
		upmin(ret, t);
	}

	return ret;
}

void run() {
	for(int i = 0; i < MAXX; i++)
		fill(ddr[i], ddr[i]+MAXX, -1);

	for(int i = 1; i <= N; i++) {
		A[Y[i]][X[i]] = i;
		S[Y[i]][X[i]]++;

		if(!dmxx[Y[i]] || X[dmxx[Y[i]]] < X[i]) dmxx[Y[i]] = i;
		if(!dmny[X[i]] || Y[dmny[X[i]]] > Y[i]) dmny[X[i]] = i;
	}
	for(int i = 1; i < MAXX; i++) for(int j = 1; j < MAXX; j++)
		S[i][j] += S[i][j-1] - S[i-1][j-1] + S[i-1][j];
	for(int i = MAXX-2; i; i--) {
		if(!dmxx[i+1]) continue;
		if(!dmxx[i] || X[dmxx[i]] <= X[dmxx[i+1]]) dmxx[i] = dmxx[i+1];
	}
	for(int i = 2; i < MAXX; i++) {
		if(!dmny[i-1]) continue;
		if(!dmny[i] || Y[dmny[i]] >= Y[dmny[i-1]]) dmny[i] = dmny[i-1];
	}
	
	/*
	{
		int mxx = *max_element(X+1, X+N+1);
		int cnt = 0;

		for(int y = 1; y < MAXX; y++) if(A[y][mxx]) {
			ddr[A[y][mxx]] = cnt*2;
			cnt++;
		}
	}

	{
		int mny = *min_element(Y+1, Y+N+1);
		int cnt = 0;

		for(int x = MAXX-1; x; x--) if(A[mny][x]) {
			ddr[A[mny][x]] = cnt*2;
			cnt++;
		}
	}
	*/

	for(int i = 1; i <= N; i++)
		g(Y[i], X[i]);
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 1; i <= N; i++)
		cin >> Y[i] >> X[i];
	
	run();

	for(int i = 1; i <= N; i++)
		Ans[i] = ddr[Y[i]][X[i]] + f(Y[i]+1, MAXX-1, X[i]+1, MAXX-1) + f(1, Y[i]-1, 1, X[i]-1);
	
	//for(int i = 1; i <= N; i++)
	//	printf("%d : %lld\n", i, ddr[Y[i]][X[i]]);
	
	init();

	for(int i = 1; i <= N; i++)
		swap(Y[i], X[i]);
	
	run();

	for(int i = 1; i <= N; i++)
		Ans[i] += ddr[Y[i]][X[i]];
	
	for(int i = 1; i <= N; i++)
		printf("%lld\n", Ans[i]);
	return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 98680 KB Output is correct
2 Correct 134 ms 98784 KB Output is correct
3 Correct 135 ms 98784 KB Output is correct
4 Correct 134 ms 98784 KB Output is correct
5 Correct 151 ms 98784 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 98824 KB Output is correct
2 Correct 142 ms 98840 KB Output is correct
3 Correct 147 ms 98932 KB Output is correct
4 Correct 137 ms 99084 KB Output is correct
5 Correct 141 ms 99084 KB Output is correct
6 Correct 139 ms 99084 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 99084 KB Output is correct
2 Correct 148 ms 99084 KB Output is correct
3 Correct 160 ms 99084 KB Output is correct
4 Correct 139 ms 99132 KB Output is correct
5 Correct 142 ms 99132 KB Output is correct
6 Correct 178 ms 99260 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 99644 KB Output is correct
2 Correct 178 ms 99644 KB Output is correct
3 Correct 172 ms 99644 KB Output is correct
4 Correct 156 ms 99644 KB Output is correct
5 Correct 156 ms 99644 KB Output is correct
6 Correct 178 ms 99832 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 104944 KB Output is correct
2 Correct 477 ms 104944 KB Output is correct
3 Correct 565 ms 104944 KB Output is correct
4 Correct 443 ms 104944 KB Output is correct
5 Correct 343 ms 104944 KB Output is correct
6 Correct 386 ms 105196 KB Output is correct
7 Correct 362 ms 105196 KB Output is correct