제출 #39567

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
39567		cheater2k	섬 항해 (CEOI13_adriatic)	C++14	100 / 100	266 ms	126728 KiB

adriatic

#include <bits/stdc++.h>
using namespace std;

const int K = 2500;
const int N = 2505;

int n, a[N][N];
int x[250005], y[250005];
int minx_l[N], maxx_r[N], miny_u[N], maxy_d[N];
long long dp1[N][N], dp2[N][N];

int get(int x0, int y0, int x1, int y1) {
	return a[x1][y1] - a[x0 - 1][y1] - a[x1][y0 - 1] + a[x0 - 1][y0 - 1];
}

pair<int,int> go_down(int x, int y) {
	return make_pair(max(x, maxx_r[y + 1]), min(y, miny_u[x - 1]));
}

pair<int,int> go_up(int x, int y) {
	return make_pair(min(x, minx_l[y - 1]), max(y, maxy_d[x + 1]));
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;

	memset(miny_u, 0x3f, sizeof miny_u);
	memset(minx_l, 0x3f, sizeof minx_l);

	for (int i = 1; i <= n; ++i) {
		cin >> x[i] >> y[i];
		a[x[i]][y[i]] = 1;
		miny_u[x[i]] = min(miny_u[x[i]], y[i]);
		maxy_d[x[i]] = max(maxy_d[x[i]], y[i]);
		minx_l[y[i]] = min(minx_l[y[i]], x[i]);
		maxx_r[y[i]] = max(maxx_r[y[i]], x[i]);
	}

	for (int i = 1; i <= K; ++i) for (int j = 1; j <= K; ++j) {
			a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
	}

	for (int i = 1; i <= K; ++i) {
		minx_l[i] = min(minx_l[i], minx_l[i - 1]);
		miny_u[i] = min(miny_u[i], miny_u[i - 1]);
		maxx_r[K + 1 - i] = max(maxx_r[K + 1 - i], maxx_r[K + 2 - i]);
		maxy_d[K + 1 - i] = max(maxy_d[K + 1 - i], maxy_d[K + 2 - i]);
	}

	for (int i = K; i >= 1; --i) {
		for (int j = 1; j <= K; ++j) {
			pair<int,int> nxt = go_down(i, j);
			dp1[i][j] = dp1[nxt.first][nxt.second] + get(i, 1, K, j);
		}
	}

	for (int i = 1; i <= K; ++i) {
		for (int j = K; j >= 1; --j) {
			pair<int,int> nxt = go_up(i, j);
			dp2[i][j] = dp2[nxt.first][nxt.second] + get(1, j, i, K);
		}
	}

	for (int i = 1; i <= n; ++i) {
		printf("%lld\n", n - 3 + dp1[x[i]][y[i]] + dp2[x[i]][y[i]]);
	}
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20