oj.uz

Submission #39567

# Submission time Handle Problem Language Result Execution time Memory
39567 2018-01-16T15:11:19 Z cheater2k Adriatic (CEOI13_adriatic) C++14
100 / 100
 266 ms 126728 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 126728 KB Output is correct
2 Correct 79 ms 126728 KB Output is correct
3 Correct 66 ms 126728 KB Output is correct
4 Correct 56 ms 126728 KB Output is correct
5 Correct 76 ms 126728 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 126728 KB Output is correct
2 Correct 79 ms 126728 KB Output is correct
3 Correct 59 ms 126728 KB Output is correct
4 Correct 79 ms 126728 KB Output is correct
5 Correct 69 ms 126728 KB Output is correct
6 Correct 99 ms 126728 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 126728 KB Output is correct
2 Correct 63 ms 126728 KB Output is correct
3 Correct 79 ms 126728 KB Output is correct
4 Correct 73 ms 126728 KB Output is correct
5 Correct 73 ms 126728 KB Output is correct
6 Correct 119 ms 126728 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 126728 KB Output is correct
2 Correct 86 ms 126728 KB Output is correct
3 Correct 96 ms 126728 KB Output is correct
4 Correct 83 ms 126728 KB Output is correct
5 Correct 69 ms 126728 KB Output is correct
6 Correct 123 ms 126728 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 126728 KB Output is correct
2 Correct 213 ms 126728 KB Output is correct
3 Correct 266 ms 126728 KB Output is correct
4 Correct 206 ms 126728 KB Output is correct
5 Correct 193 ms 126728 KB Output is correct
6 Correct 206 ms 126728 KB Output is correct
7 Correct 246 ms 126728 KB Output is correct