oj.uz

Submission #680078

# Submission time Handle Problem Language Result Execution time Memory
680078 2023-01-09T21:22:58 Z GusterGoose27 Adriatic (CEOI13_adriatic) C++11
100 / 100
 345 ms 232880 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int MAXN = 25e4;
const int m = 2500;
const int inf = 1e9;

ll dp[m][m][2]; // top left, or bottom right
bool point[m][m];
int pre[m][m];
int extr[m][m][4]; // right, up, left, down

pii points[MAXN];
int n;

int cnt(int x, int y1, int y2) {
	return pre[x][y2] - (y1 ? pre[x][y1-1] : 0);
}

int cnt(int x1, int x2, int y1, int y2) {
	if (x1 > x2 || y1 > y2) return 0;
	return cnt(x2, y1, y2) - (x1 ? cnt(x1-1, y1, y2) : 0);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x, y; cin >> x >> y;
		x--; y--;
		points[i] = pii(x, y);
		point[x][y] = 1;
	}
	vector<pii> lft; // basically stores the left hull
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < m; j++) {
			pre[i][j] = point[i][j];
			extr[i][j][2] = inf;
			extr[i][j][3] = inf;
			if (i) {
				pre[i][j] += pre[i-1][j];
				extr[i][j][2] = min(extr[i][j][2], extr[i-1][j][2]);
				extr[i][j][3] = min(extr[i][j][3], extr[i-1][j][3]);
			}
			if (j) {
				pre[i][j] += pre[i][j-1];
				extr[i][j][2] = min(extr[i][j][2], extr[i][j-1][2]);
				extr[i][j][3] = min(extr[i][j][3], extr[i][j-1][3]);
			}
			if (i && j && point[i-1][j-1]) {
				extr[i][j][2] = min(extr[i][j][2], i-1);
				extr[i][j][3] = min(extr[i][j][3], j-1);
			}
			if (i && j) pre[i][j] -= pre[i-1][j-1];
		}
	}
	for (int i = m-1; i >= 0; i--) {
		for (int j = m-1; j >= 0; j--) {
			extr[i][j][0] = -inf;
			extr[i][j][1] = -inf;
			if (i < m-1) {
				extr[i][j][0] = max(extr[i][j][0], extr[i+1][j][0]);
				extr[i][j][1] = max(extr[i][j][1], extr[i+1][j][1]);
			}
			if (j < m-1) {
				extr[i][j][0] = max(extr[i][j][0], extr[i][j+1][0]);
				extr[i][j][1] = max(extr[i][j][1], extr[i][j+1][1]);
			}
			if (i < m-1 && j < m-1 && point[i+1][j+1]) {
				extr[i][j][0] = max(extr[i][j][0], i+1);
				extr[i][j][1] = max(extr[i][j][1], j+1);
			}
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = m-1; j >= 0; j--) {
			int x = min(i, extr[i][j][2]);
			int y = max(j, extr[i][j][1]);
			if (x == i && y == j) continue;
			dp[i][j][0] = 2*(cnt(0, i, j, m-1))-cnt(0, x, y, m-1)+dp[x][y][0];
		}
	}
	for (int i = m-1; i >= 0; i--) {
		for (int j = 0; j < m; j++) {
			int x = max(i, extr[i][j][0]);
			int y = min(j, extr[i][j][3]);
			if (x == i && y == j) continue;
			dp[i][j][1] = 2*(cnt(i, m-1, 0, j))-cnt(x, m-1, 0, y)+dp[x][y][1];
		}
	}
	for (int i = 0; i < n; i++) {
		int x = points[i].first;
		int y = points[i].second;
		cout << (dp[x][y][0]+dp[x][y][1]-4+cnt(0, x-1, 0, y-1)+cnt(x+1, m-1, y+1, m-1)) << "\n";
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 220752 KB Output is correct
2 Correct 180 ms 220940 KB Output is correct
3 Correct 175 ms 220856 KB Output is correct
4 Correct 170 ms 220500 KB Output is correct
5 Correct 173 ms 220708 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 224116 KB Output is correct
2 Correct 182 ms 224280 KB Output is correct
3 Correct 178 ms 224244 KB Output is correct
4 Correct 220 ms 220712 KB Output is correct
5 Correct 171 ms 221252 KB Output is correct
6 Correct 190 ms 223048 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 226140 KB Output is correct
2 Correct 178 ms 226440 KB Output is correct
3 Correct 194 ms 226332 KB Output is correct
4 Correct 186 ms 221192 KB Output is correct
5 Correct 190 ms 221476 KB Output is correct
6 Correct 260 ms 226600 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 227200 KB Output is correct
2 Correct 181 ms 227132 KB Output is correct
3 Correct 212 ms 227076 KB Output is correct
4 Correct 199 ms 222156 KB Output is correct
5 Correct 182 ms 222388 KB Output is correct
6 Correct 271 ms 227104 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 232644 KB Output is correct
2 Correct 277 ms 232524 KB Output is correct
3 Correct 300 ms 232620 KB Output is correct
4 Correct 290 ms 228428 KB Output is correct
5 Correct 259 ms 228696 KB Output is correct
6 Correct 344 ms 232704 KB Output is correct
7 Correct 345 ms 232880 KB Output is correct