oj.uz

Submission #497856

# Submission time Handle Problem Language Result Execution time Memory
497856 2021-12-24T01:49:00 Z SirCovidThe19th Adriatic (CEOI13_adriatic) C++17
100 / 100
 816 ms 125484 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 - 1) - 2<<endl;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 123428 KB Output is correct
2 Correct 375 ms 123428 KB Output is correct
3 Correct 364 ms 123436 KB Output is correct
4 Correct 363 ms 123424 KB Output is correct
5 Correct 367 ms 123372 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 123480 KB Output is correct
2 Correct 383 ms 123480 KB Output is correct
3 Correct 365 ms 123432 KB Output is correct
4 Correct 370 ms 123396 KB Output is correct
5 Correct 368 ms 123400 KB Output is correct
6 Correct 376 ms 123404 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 123408 KB Output is correct
2 Correct 375 ms 123524 KB Output is correct
3 Correct 375 ms 123460 KB Output is correct
4 Correct 374 ms 123460 KB Output is correct
5 Correct 368 ms 123408 KB Output is correct
6 Correct 405 ms 123460 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 123672 KB Output is correct
2 Correct 412 ms 123668 KB Output is correct
3 Correct 419 ms 123632 KB Output is correct
4 Correct 403 ms 123696 KB Output is correct
5 Correct 430 ms 123576 KB Output is correct
6 Correct 436 ms 123688 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 800 ms 125380 KB Output is correct
2 Correct 809 ms 125484 KB Output is correct
3 Correct 787 ms 125432 KB Output is correct
4 Correct 781 ms 125388 KB Output is correct
5 Correct 757 ms 125384 KB Output is correct
6 Correct 792 ms 125392 KB Output is correct
7 Correct 816 ms 125388 KB Output is correct