oj.uz

Submission #777982

# Submission time Handle Problem Language Result Execution time Memory
777982 2023-07-10T00:47:04 Z NK_ Adriatic (CEOI13_adriatic) C++17
100 / 100
 166 ms 78072 KB 
// 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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 73872 KB Output is correct
2 Correct 69 ms 73908 KB Output is correct
3 Correct 72 ms 73804 KB Output is correct
4 Correct 59 ms 73804 KB Output is correct
5 Correct 71 ms 73812 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 73932 KB Output is correct
2 Correct 74 ms 73936 KB Output is correct
3 Correct 71 ms 73932 KB Output is correct
4 Correct 59 ms 73936 KB Output is correct
5 Correct 69 ms 73892 KB Output is correct
6 Correct 75 ms 73836 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 73988 KB Output is correct
2 Correct 71 ms 73988 KB Output is correct
3 Correct 75 ms 73992 KB Output is correct
4 Correct 61 ms 73996 KB Output is correct
5 Correct 78 ms 74012 KB Output is correct
6 Correct 86 ms 73940 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 74360 KB Output is correct
2 Correct 83 ms 74356 KB Output is correct
3 Correct 79 ms 74416 KB Output is correct
4 Correct 68 ms 74348 KB Output is correct
5 Correct 77 ms 74260 KB Output is correct
6 Correct 91 ms 74324 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 78072 KB Output is correct
2 Correct 166 ms 77800 KB Output is correct
3 Correct 150 ms 77820 KB Output is correct
4 Correct 133 ms 77780 KB Output is correct
5 Correct 121 ms 77808 KB Output is correct
6 Correct 135 ms 78056 KB Output is correct
7 Correct 128 ms 78064 KB Output is correct