Submission #680078

#	Time	Username	Problem	Language	Result	Execution time	Memory
680078		GusterGoose27	Adriatic (CEOI13_adriatic)	C++11	100 / 100	345 ms	232880 KiB

adriatic

#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 / 25
• Subtask 2: 25 / 25
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20