oj.uz

Submission #265379

# Submission time Handle Problem Language Result Execution time Memory
265379 2020-08-14T17:01:49 Z Sorting Adriatic (CEOI13_adriatic) C++17
100 / 100
 824 ms 258040 KB 
#include <bits/stdc++.h>

using namespace std;

const int k_N = 25e4 + 3;
const int k_Max = 2500;
const int k_Max3 = k_Max + 3;

int n;
array<int, 2> p[k_N];

long long dp1[k_Max3][k_Max3], dp2[k_Max3][k_Max3];
int minR[k_Max3][k_Max3], maxR[k_Max3][k_Max3];
int minC[k_Max3][k_Max3], maxC[k_Max3][k_Max3];

int cnt1[k_Max3][k_Max3], cnt2[k_Max3][k_Max3];
bool b[k_Max3][k_Max3];

void init_dp(){
    for(int i = 1; i <= k_Max; ++i){
        for(int j = k_Max; j >= 1; --j){
            int x = i, y = j;
            x = min(x, minR[i - 1][j - 1]);
            y = max(y, maxC[i + 1][j + 1]);

            if(cnt1[i][j] == 0) dp1[i][j] = 0;
            else dp1[i][j] = dp1[x][y] + cnt1[i][j];
        }
    }

    for(int i = k_Max; i >= 1; --i){
        for(int j = 1; j <= k_Max; ++j){
            int x = i, y = j;
            x = max(x, maxR[i + 1][j + 1]);
            y = min(y, minC[i - 1][j - 1]);

            if(cnt2[i][j] == 0) dp2[i][j] = 0;
            else dp2[i][j] = dp2[x][y] + cnt2[i][j];
        }
    }
}

void init_min_max(){
    for(int i = 0; i < k_Max3; ++i){
        for(int j = 0; j < k_Max3; ++j){
            maxC[i][j] = 0;
            maxR[i][j] = 0;
            minC[i][j] = k_Max + 1;
            minR[i][j] = k_Max + 1;
        }
    }

    for(int i = 0; i < n; ++i){
        auto [r, c] = p[i];
        maxC[r][c] = c;
        minC[r][c] = c;
        maxR[r][c] = r;
        minR[r][c] = r;
    }

    for(int i = k_Max; i >= 1; --i){
        for(int j = k_Max; j >= 1; --j){
            maxC[i][j] = max(maxC[i][j], maxC[i][j + 1]);
            maxR[i][j] = max(maxR[i][j], maxR[i][j + 1]);
        }
    }
    for(int j = k_Max; j >= 1; --j){
        for(int i = k_Max; i >= 1; --i){
            maxC[i][j] = max(maxC[i][j], maxC[i + 1][j]);
            maxR[i][j] = max(maxR[i][j], maxR[i + 1][j]);
        }
    }

    for(int i = 1; i <= k_Max; ++i){
        for(int j = 1; j <= k_Max; ++j){
            minC[i][j] = min(minC[i][j], minC[i][j - 1]);
            minR[i][j] = min(minR[i][j], minR[i][j - 1]); 
        }
    }
    for(int j = 1; j <= k_Max; ++j){
        for(int i = 1; i <= k_Max; ++i){
            minC[i][j] = min(minC[i][j], minC[i - 1][j]);
            minR[i][j] = min(minR[i][j], minR[i - 1][j]); 
        }
    }

    /*cout << "minC: " << endl;
    for(int i = 1; i <= 7; ++i){
        for(int j = 1; j <= 8; ++j){
            cout << minC[i][j] << " "; 
        }
        cout << endl;
    }
    cout << "maxC: " << endl;
    for(int i = 1; i <= 7; ++i){
        for(int j = 1; j <= 8; ++j){
            cout << maxC[i][j] << " "; 
        }
        cout << endl;
    }
    cout << "minR: " << endl;
    for(int i = 1; i <= 7; ++i){
        for(int j = 1; j <= 8; ++j){
            cout << minR[i][j] << " "; 
        }
        cout << endl;
    }
    cout << "maxR: " << endl;
    for(int i = 1; i <= 7; ++i){
        for(int j = 1; j <= 8; ++j){
            cout << maxR[i][j] << " "; 
        }
        cout << endl;
    }*/
}

void init_cnt(){
    for(int i = 0; i < n; ++i){
        auto [r, c] = p[i];
        cnt1[r][c] = 1;
        cnt2[r][c] = 1;
        b[r][c] = true; 
    }

    for(int i = 1; i <= k_Max; ++i)
        for(int j = k_Max; j >= 1; --j)
            cnt1[i][j] += cnt1[i][j + 1];
    for(int j = k_Max; j >= 1; --j)
        for(int i = 1; i <= k_Max; ++i)
            cnt1[i][j] += cnt1[i - 1][j];

    for(int i = k_Max; i >= 1; --i)
        for(int j = 1; j <= k_Max; ++j)
            cnt2[i][j] += cnt2[i][j - 1];
    for(int j = 1; j <= k_Max; ++j)
        for(int i = k_Max; i >= 1; --i)
            cnt2[i][j] += cnt2[i + 1][j];

    /*cout << "cnt1: " << endl;
    for(int i = 1; i <= 7; ++i){
        for(int j = 1; j <= 8; ++j){
            cout << cnt1[i][j] << " "; 
        }
        cout << endl;
    }

    cout << "cnt2: " << endl;
    for(int i = 1; i <= 7; ++i){
        for(int j = 1; j <= 8; ++j){
            cout << cnt2[i][j] << " "; 
        }
        cout << endl;
    }*/
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> p[i][0] >> p[i][1];

    init_cnt();
    init_min_max();
    init_dp();

    for(int i = 0; i < n; ++i){
        auto [r, c] = p[i];
        cout << dp1[r][c] + dp2[r][c] + (n - 1) - 2 << "\n";
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 245880 KB Output is correct
2 Correct 674 ms 245880 KB Output is correct
3 Correct 677 ms 245880 KB Output is correct
4 Correct 669 ms 245588 KB Output is correct
5 Correct 677 ms 245628 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 249096 KB Output is correct
2 Correct 716 ms 249240 KB Output is correct
3 Correct 685 ms 249280 KB Output is correct
4 Correct 669 ms 245752 KB Output is correct
5 Correct 689 ms 246264 KB Output is correct
6 Correct 691 ms 248032 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 251128 KB Output is correct
2 Correct 699 ms 251512 KB Output is correct
3 Correct 709 ms 251384 KB Output is correct
4 Correct 671 ms 246304 KB Output is correct
5 Correct 683 ms 246520 KB Output is correct
6 Correct 766 ms 251688 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 752 ms 252408 KB Output is correct
2 Correct 691 ms 252152 KB Output is correct
3 Correct 701 ms 252248 KB Output is correct
4 Correct 681 ms 247176 KB Output is correct
5 Correct 700 ms 247416 KB Output is correct
6 Correct 745 ms 252332 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 823 ms 258040 KB Output is correct
2 Correct 801 ms 257528 KB Output is correct
3 Correct 822 ms 257600 KB Output is correct
4 Correct 808 ms 253688 KB Output is correct
5 Correct 783 ms 253640 KB Output is correct
6 Correct 816 ms 257656 KB Output is correct
7 Correct 824 ms 257912 KB Output is correct