oj.uz

Submission #257213

# Submission time Handle Problem Language Result Execution time Memory
257213 2020-08-03T21:53:44 Z doowey Adriatic (CEOI13_adriatic) C++14
60 / 100
 374 ms 262148 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];
int cnt_u[N][N];
int cnt_d[N][N];
ll dis_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 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,(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) + 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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 247164 KB Output is correct
2 Correct 269 ms 247260 KB Output is correct
3 Correct 267 ms 247220 KB Output is correct
4 Correct 268 ms 246904 KB Output is correct
5 Correct 265 ms 247164 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 251256 KB Output is correct
2 Correct 270 ms 252024 KB Output is correct
3 Correct 270 ms 251384 KB Output is correct
4 Correct 261 ms 247216 KB Output is correct
5 Correct 262 ms 247544 KB Output is correct
6 Correct 297 ms 249464 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 255224 KB Output is correct
2 Correct 295 ms 260472 KB Output is correct
3 Correct 300 ms 255608 KB Output is correct
4 Correct 286 ms 248312 KB Output is correct
5 Correct 271 ms 247960 KB Output is correct
6 Correct 309 ms 256888 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 257528 KB Output is correct
2 Runtime error 269 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 261752 KB Output is correct
2 Runtime error 364 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -