Submission #497856

#	Time	Username	Problem	Language	Result	Execution time	Memory
497856		SirCovidThe19th	Adriatic (CEOI13_adriatic)	C++17	100 / 100	816 ms	125484 KiB

adriatic

#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];
    }
}
 
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) - 2<<endl;
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20