This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define vvi vector<vector<int>>
#define init mx, vector<int>(mx, 0)
const int mx = 2505;
void rot(vvi &A){
int tmp[mx][mx];
FOR(it, 0, 2){ //rotate 180
FOR(i, 0, mx) FOR(j, 0, mx) tmp[j][mx - i - 1] = A[i][j];
FOR(i, 0, mx) FOR(j, 0, mx) A[i][j] = tmp[i][j];
}
}
void calc(vvi A, vvi &dp){
int pre[mx][mx] = {}, mxR[mx] = {}, mnC[mx]; memset(mnC, 0x3f, sizeof(mnC));
for (int i = mx - 2; i; i--) FOR(j, 1, mx){
pre[i][j] = A[i][j] + pre[i + 1][j] + pre[i][j - 1] - pre[i + 1][j - 1];
if (A[i][j]){
mxR[j] = max(mxR[j], i); //largest row to the right/at col i
mnC[i] = min(mnC[i], j); //smallest col above/at row i
}
}
FOR(i, 1, mx) mnC[i] = min(mnC[i], mnC[i - 1]);
for (int i = mx - 2; i; i--) mxR[i] = max(mxR[i], mxR[i + 1]);
for (int i = mx - 2; i; i--) FOR(j, 1, mx){
int r = max(i, mxR[j + 1]), c = min(j, mnC[i - 1]);
dp[i][j] = dp[r][c] + pre[i][j] - (A[i][j]);
}
}
int main(){
int n; cin >> n; pair<int, int> pts[n];
vvi A(init), dp1(init), dp2(init);
for (auto &[x, y] : pts) cin >> x >> y, A[x][y]++;
calc(A, dp1);
rot(A); calc(A, dp2); rot(dp2);
for (auto [x, y] : pts) cout<<dp1[x][y] + dp2[x][y] + (n - 1)<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |