Submission #257212

#	Time	Username	Problem	Language	Result	Execution time	Memory
257212		doowey	Adriatic (CEOI13_adriatic)	C++14	60 / 100	358 ms	262148 KiB

adriatic

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 2510;
const int M = (int)250101;
int dis_u[N][N];
int cnt_u[N][N];
int cnt_d[N][N];
int dis_d[N][N];
int has[N][N];
int lowi[N][N];
int mxj[N][N];
int lowj[N][N];
int mxi[N][N];
int res[M];
int ccc[N][N];
int uuu[N][N];

int main(){
    fastIO;
    int n;
    cin >> n;
    int x, y;
    for(int i = 1; i <= n; i ++ ){
        cin >> x >> y;
        has[x][y]=i;
    }
    for(int i = 0 ; i < N ; i ++ ){
        for(int j = 0 ; j < N ; j ++ ){
            lowi[i][j]=N-1;
            lowj[i][j]=N-1;
            if(has[i][j]){
                lowi[i][j]=i;
                lowj[i][j]=j;
                ccc[i][j] = 1;
            }

            if(i>0){
                ccc[i][j] += ccc[i-1][j];
                lowi[i][j]=min(lowi[i][j],lowi[i-1][j]);
                lowj[i][j]=min(lowj[i][j],lowj[i-1][j]);
            }
            if(j>0){
                ccc[i][j] += ccc[i][j - 1];
                lowi[i][j]=min(lowi[i][j],lowi[i][j-1]);
                lowj[i][j]=min(lowj[i][j],lowj[i][j-1]);
            }
            if(i > 0 && j > 0)
                ccc[i][j] -= ccc[i - 1][j - 1];
        }
    }
    for(int i = N - 3; i >= 0 ; i -- ){
        for(int j = N - 3; j >= 0 ; j -- ){
            if(has[i][j]) {
                mxj[i][j] = j;
                mxi[i][j] = i;
                uuu[i][j] = 1;
            }
            mxj[i][j] = max(mxj[i + 1][j], mxj[i][j]);
            mxj[i][j] = max(mxj[i][j + 1], mxj[i][j]);
            mxi[i][j] = max(mxi[i + 1][j], mxi[i][j]);
            mxi[i][j] = max(mxi[i][j + 1], mxi[i][j]);
            uuu[i][j] += uuu[i + 1][j] + uuu[i][j + 1] - uuu[i + 1][j + 1];
        }
    }
    int ci, cj;
    for(int i = 1; i < N - 3; i ++){
        for(int j = N - 3; j >= 1 ; j --  ){
            cnt_u[i][j] = (has[i][j] > 0);
            cnt_u[i][j] += cnt_u[i-1][j];
            cnt_u[i][j] += cnt_u[i][j+1];
            cnt_u[i][j] -= cnt_u[i - 1][j + 1];
            dis_u[i][j] += cnt_u[i][j];

            if(cnt_u[i][j] > (has[i][j] > 0)){
                ci = min(i,lowi[i-1][j-1]);
                cj = max(j,mxj[i+1][j+1]);
                dis_u[i][j] += dis_u[ci][cj];
            }
        }
    }
    for(int i = N - 3; i >= 1 ; i -- ){
        for(int j = 1 ; j < N - 3; j ++ ){
            cnt_d[i][j] = (has[i][j] > 0);
            cnt_d[i][j] += cnt_d[i+1][j];
            cnt_d[i][j] += cnt_d[i][j-1];
            cnt_d[i][j] -= cnt_d[i+1][j-1];
            dis_d[i][j] += cnt_d[i][j];
            if(cnt_d[i][j] > (has[i][j] > 0)){
                ci = max(i,mxi[i+1][j+1]);
                cj = min(j,lowj[i-1][j-1]);
                dis_d[i][j] += dis_d[ci][cj];
            }
        }
    }
    for(int i = 0 ; i < N ; i ++ ){
        for(int j = 0 ; j < N ; j ++ ){
            if(has[i][j]){
                res[has[i][j]] += (cnt_d[i][j]-1) + (cnt_u[i][j]-1) + ccc[i-1][j-1] + uuu[i+1][j+1] + (dis_u[i][j]-1) + (dis_d[i][j] - 1);
            }
        }
    }
    for(int i = 1; i <= n; i ++ )
        cout << res[i] << "\n";
    return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 10 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20