Submission #265379

#	Time	Username	Problem	Language	Result	Execution time	Memory
265379		Sorting	Adriatic (CEOI13_adriatic)	C++17	100 / 100	824 ms	258040 KiB

adriatic

#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 / 25
• Subtask 2: 25 / 25
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20