oj.uz

Submission #257214

# Submission time Handle Problem Language Result Execution time Memory
257214 2020-08-03T21:57:38 Z doowey Adriatic (CEOI13_adriatic) C++14
100 / 100
 381 ms 251768 KB 
#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;
ll dis_u[N][N];
ll dis_d[N][N];
int cnt_u[N][N];
int cnt_d[N][N];
int has[N][N];
short lowi[N][N];
short mxj[N][N];
short lowj[N][N];
short mxi[N][N];
int res[M];
int ccc[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];
            if(has[i][j]){
                res[has[i][j]] += ccc[i - 1][j - 1];
            }
        }
    }
    for(int i = 0 ; i < N ; i ++ ){
        for(int j = 0; j < N ; j ++ ){
            ccc[i][j] = 0;
        }
    }
    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;
                ccc[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]);
            ccc[i][j] += ccc[i + 1][j] + ccc[i][j + 1] - ccc[i + 1][j + 1];
            if(has[i][j]){
                res[has[i][j]] += ccc[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,(int)lowi[i-1][j-1]);
                cj = max(j,(int)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,(int)mxi[i+1][j+1]);
                cj = min(j,(int)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) + (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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 222456 KB Output is correct
2 Correct 260 ms 222488 KB Output is correct
3 Correct 269 ms 222584 KB Output is correct
4 Correct 289 ms 222200 KB Output is correct
5 Correct 270 ms 222328 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 226728 KB Output is correct
2 Correct 271 ms 227448 KB Output is correct
3 Correct 261 ms 226680 KB Output is correct
4 Correct 260 ms 222620 KB Output is correct
5 Correct 267 ms 222840 KB Output is correct
6 Correct 271 ms 224760 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 230520 KB Output is correct
2 Correct 270 ms 235896 KB Output is correct
3 Correct 274 ms 231032 KB Output is correct
4 Correct 252 ms 223608 KB Output is correct
5 Correct 261 ms 223352 KB Output is correct
6 Correct 309 ms 232184 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 232952 KB Output is correct
2 Correct 285 ms 246776 KB Output is correct
3 Correct 280 ms 233592 KB Output is correct
4 Correct 260 ms 225656 KB Output is correct
5 Correct 269 ms 224760 KB Output is correct
6 Correct 300 ms 233292 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 236152 KB Output is correct
2 Correct 381 ms 251768 KB Output is correct
3 Correct 369 ms 246136 KB Output is correct
4 Correct 333 ms 234616 KB Output is correct
5 Correct 335 ms 231672 KB Output is correct
6 Correct 371 ms 239736 KB Output is correct
7 Correct 374 ms 239608 KB Output is correct