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