Submission #777982

#	Time	Username	Problem	Language	Result	Execution time	Memory
777982		NK_	Adriatic (CEOI13_adriatic)	C++17	100 / 100	166 ms	78072 KiB

adriatic

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

const int nax = 2503;

int P[nax][nax];
int mxr[nax], mxc[nax], mnr[nax], mnc[nax];
int dp[2][nax][nax];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	for(int i = 0; i < nax; i++) {
		for(int j = 0; j < nax; j++) {
			dp[0][i][j] = dp[1][i][j] = 0;
			P[i][j] = 0;
		}

		mnr[i] = nax + 1, mnc[i] = nax + 1;
		mxr[i] = -1, mxc[i] = -1;
	}


	int N; cin >> N;
	vector<int> RI(N), CI(N);
	for(int i = 0; i < N; i++) {
		int r, c; cin >> r >> c;
		mxr[c] = max(mxr[c], r), mnr[c] = min(mnr[c], r);
		mxc[r] = max(mxc[r], c), mnc[r] = min(mnc[r], c);

		P[r][c]++;
		RI[i] = r, CI[i] = c;
	}

	for(int i = 0; i < nax; i++) for(int j = 0; j < nax; j++) {
		if (i) P[i][j] += P[i-1][j];
		if (j) P[i][j] += P[i][j-1];
		if (i && j) P[i][j] -= P[i-1][j-1];
	}

	auto qry = [&](int r, int c, int R, int C) { 
		if (r > R || c > C) return 0;
		return P[R][C] - (r ? P[r-1][C] : 0) - (c ? P[R][c-1] : 0) + (r && c ? P[r-1][c-1] : 0);
	};

	for(int i = 1; i < nax; i++) mnc[i] = min(mnc[i], mnc[i-1]), mnr[i] = min(mnr[i], mnr[i-1]);
	for(int i = nax - 2; i >= 1; i--) mxc[i] = max(mxc[i], mxc[i+1]), mxr[i] = max(mxr[i], mxr[i+1]);

	// TOP RIGHT
	for(int r = 1; r < nax - 1; r++) for(int c = nax - 2; c >= 1; c--) {
		dp[0][r][c] = qry(1, c, r, nax - 1); 
		if (!dp[0][r][c]) continue;
		int R = min(r, mnr[c-1]), C = max(c, mxc[r+1]);
		dp[0][r][c] += dp[0][R][C];
	}

	// BOTTOM LEFT
	for(int r = nax - 2; r >= 1; r--) for(int c = 1; c < nax - 1; c++) {
		dp[1][r][c] = qry(r, 1, nax - 1, c);
		if (!dp[1][r][c]) continue;
		int R = max(r, mxr[c+1]), C = min(c, mnc[r-1]);
		dp[1][r][c] += dp[1][R][C];
	}

	for(int i = 0; i < N; i++) {
		int r = RI[i], c = CI[i];
		int ans = (dp[0][r][c] - 1) + (dp[1][r][c] - 1) + (N - 1);
		cout << ans << nl;
	}

    return 0;
}

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