oj.uz

Submission #777980

# Submission time Handle Problem Language Result Execution time Memory
777980 2023-07-10T00:46:02 Z NK_ Adriatic (CEOI13_adriatic) C++17
100 / 100
 173 ms 80340 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 = 2505;

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

void print(int A[nax][nax]) {
	for(int i = 0; i < nax; i++) {
		for(int j = 0; j < nax; j++) cout << A[i][j] << " ";
		cout << endl;
	}
	cout << endl << endl;
}

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]);

	// print(P);

	// 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];
	}

	// print(dp[0]);

	// 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];
	}

	// print(dp[1]);

	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 74 ms 74020 KB Output is correct
2 Correct 70 ms 74024 KB Output is correct
3 Correct 72 ms 74020 KB Output is correct
4 Correct 62 ms 74024 KB Output is correct
5 Correct 72 ms 73928 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 74064 KB Output is correct
2 Correct 74 ms 74048 KB Output is correct
3 Correct 74 ms 74052 KB Output is correct
4 Correct 68 ms 73932 KB Output is correct
5 Correct 78 ms 74100 KB Output is correct
6 Correct 79 ms 74108 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 74116 KB Output is correct
2 Correct 83 ms 74024 KB Output is correct
3 Correct 75 ms 74076 KB Output is correct
4 Correct 63 ms 74096 KB Output is correct
5 Correct 73 ms 74120 KB Output is correct
6 Correct 88 ms 74108 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 74616 KB Output is correct
2 Correct 83 ms 74544 KB Output is correct
3 Correct 86 ms 74568 KB Output is correct
4 Correct 78 ms 74540 KB Output is correct
5 Correct 78 ms 74572 KB Output is correct
6 Correct 91 ms 74560 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 80184 KB Output is correct
2 Correct 173 ms 79884 KB Output is correct
3 Correct 148 ms 79904 KB Output is correct
4 Correct 127 ms 79584 KB Output is correct
5 Correct 121 ms 80104 KB Output is correct
6 Correct 126 ms 80144 KB Output is correct
7 Correct 126 ms 80340 KB Output is correct