oj.uz

Submission #497847

# Submission time Handle Problem Language Result Execution time Memory
497847 2021-12-24T01:15:08 Z SirCovidThe19th Adriatic (CEOI13_adriatic) C++17
100 / 100
 888 ms 125392 KB 
#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 - 3<<endl;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 123516 KB Output is correct
2 Correct 418 ms 123388 KB Output is correct
3 Correct 363 ms 123436 KB Output is correct
4 Correct 376 ms 123368 KB Output is correct
5 Correct 389 ms 123416 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 123392 KB Output is correct
2 Correct 384 ms 123412 KB Output is correct
3 Correct 439 ms 123500 KB Output is correct
4 Correct 372 ms 123384 KB Output is correct
5 Correct 382 ms 123448 KB Output is correct
6 Correct 380 ms 123428 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 123480 KB Output is correct
2 Correct 379 ms 123500 KB Output is correct
3 Correct 460 ms 123440 KB Output is correct
4 Correct 392 ms 123460 KB Output is correct
5 Correct 400 ms 123452 KB Output is correct
6 Correct 424 ms 123472 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 123632 KB Output is correct
2 Correct 441 ms 123624 KB Output is correct
3 Correct 455 ms 123564 KB Output is correct
4 Correct 420 ms 123604 KB Output is correct
5 Correct 413 ms 123580 KB Output is correct
6 Correct 493 ms 123628 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 821 ms 125392 KB Output is correct
2 Correct 830 ms 125384 KB Output is correct
3 Correct 888 ms 125368 KB Output is correct
4 Correct 806 ms 125392 KB Output is correct
5 Correct 775 ms 125380 KB Output is correct
6 Correct 830 ms 125332 KB Output is correct
7 Correct 875 ms 125384 KB Output is correct