oj.uz

Submission #777981

# Submission time Handle Problem Language Result Execution time Memory
777981 2023-07-10T00:46:47 Z NK_ Adriatic (CEOI13_adriatic) C++17
100 / 100
 184 ms 79680 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];

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 69 ms 73812 KB Output is correct
2 Correct 69 ms 73800 KB Output is correct
3 Correct 70 ms 73904 KB Output is correct
4 Correct 66 ms 73808 KB Output is correct
5 Correct 74 ms 73900 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 73928 KB Output is correct
2 Correct 71 ms 73936 KB Output is correct
3 Correct 71 ms 73888 KB Output is correct
4 Correct 60 ms 73924 KB Output is correct
5 Correct 73 ms 73860 KB Output is correct
6 Correct 73 ms 73932 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 73928 KB Output is correct
2 Correct 73 ms 73988 KB Output is correct
3 Correct 83 ms 73940 KB Output is correct
4 Correct 63 ms 73916 KB Output is correct
5 Correct 81 ms 74004 KB Output is correct
6 Correct 86 ms 73992 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 74448 KB Output is correct
2 Correct 82 ms 74424 KB Output is correct
3 Correct 80 ms 74452 KB Output is correct
4 Correct 73 ms 74428 KB Output is correct
5 Correct 76 ms 74468 KB Output is correct
6 Correct 93 ms 74492 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 79596 KB Output is correct
2 Correct 184 ms 79336 KB Output is correct
3 Correct 152 ms 79344 KB Output is correct
4 Correct 118 ms 79416 KB Output is correct
5 Correct 120 ms 79340 KB Output is correct
6 Correct 137 ms 79680 KB Output is correct
7 Correct 126 ms 79564 KB Output is correct