oj.uz

Submission #497850

# Submission time Handle Problem Language Result Execution time Memory
497850 2021-12-24T01:17:35 Z SirCovidThe19th Adriatic (CEOI13_adriatic) C++17
0 / 100
 812 ms 125452 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] - (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;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 123328 KB Output is correct
2 Correct 366 ms 123400 KB Output is correct
3 Correct 365 ms 123388 KB Output is correct
4 Incorrect 368 ms 123400 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 393 ms 123384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 380 ms 123472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 437 ms 123604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 812 ms 125452 KB Output isn't correct
2 Halted 0 ms 0 KB -