oj.uz

Submission #92563

# Submission time Handle Problem Language Result Execution time Memory
92563 2019-01-03T12:39:01 Z maruii Wall (IOI14_wall) C++17
100 / 100
 1218 ms 64460 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 1<<21;
int *fin;
struct ST{
    int mn[2*SIZE], mx[2*SIZE];
    void update(int nn, int ns, int ne, int s, int e, int x, int q){
        if(ns>e || ne<s) return;
        if(s<=ns && ne<=e){
            if(q==1){
                mn[nn] = max(mn[nn], x);
                mx[nn] = max(mx[nn], x);
            } else if(q==2){
                mn[nn] = min(mn[nn], x);
                mx[nn] = min(mx[nn], x);
            }
            if(ns==ne) fin[ns] = mx[nn];
            return;
        }
        int m =(ns+ne)/2;
        int l = nn*2, r = l+1;
        mn[l] = min(mn[l], mn[nn]); mn[r] = min(mn[r], mn[nn]);
        mx[l] = min(mx[l], mn[nn]); mx[r] = min(mx[r], mn[nn]);
        mn[l] = max(mn[l], mx[nn]); mn[r] = max(mn[r], mx[nn]);
        mx[l] = max(mx[l], mx[nn]); mx[r] = max(mx[r], mx[nn]);
        mx[nn] = 0; mn[nn] = 1e9;
        update(l, ns, m, s, e, x, q);
        update(r, m+1, ne, s, e, x, q);
    }
}seg;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    fin = finalHeight;
    for(int i=0; i<k; ++i){
        seg.update(1, 0, n-1, left[i], right[i], height[i], op[i]);
    }
    for(int i=0; i<n; ++i)
        seg.update(1, 0, n-1, i, i, 0, 0);
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 8 ms 852 KB Output is correct
5 Correct 7 ms 888 KB Output is correct
6 Correct 7 ms 888 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 141 ms 13968 KB Output is correct
3 Correct 161 ms 8028 KB Output is correct
4 Correct 477 ms 16504 KB Output is correct
5 Correct 292 ms 16888 KB Output is correct
6 Correct 286 ms 16976 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 8 ms 888 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 7 ms 888 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 141 ms 14016 KB Output is correct
9 Correct 164 ms 8056 KB Output is correct
10 Correct 467 ms 16504 KB Output is correct
11 Correct 292 ms 17016 KB Output is correct
12 Correct 286 ms 16960 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 196 ms 14112 KB Output is correct
15 Correct 31 ms 2084 KB Output is correct
16 Correct 472 ms 16632 KB Output is correct
17 Correct 292 ms 16904 KB Output is correct
18 Correct 285 ms 16888 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 8 ms 888 KB Output is correct
5 Correct 8 ms 760 KB Output is correct
6 Correct 7 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 143 ms 13944 KB Output is correct
9 Correct 163 ms 8028 KB Output is correct
10 Correct 491 ms 16420 KB Output is correct
11 Correct 298 ms 16888 KB Output is correct
12 Correct 285 ms 17064 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 145 ms 13944 KB Output is correct
15 Correct 31 ms 2040 KB Output is correct
16 Correct 467 ms 16760 KB Output is correct
17 Correct 291 ms 16888 KB Output is correct
18 Correct 287 ms 16936 KB Output is correct
19 Correct 1120 ms 64460 KB Output is correct
20 Correct 1065 ms 62072 KB Output is correct
21 Correct 1072 ms 64248 KB Output is correct
22 Correct 1071 ms 61736 KB Output is correct
23 Correct 1095 ms 61712 KB Output is correct
24 Correct 1218 ms 61664 KB Output is correct
25 Correct 1062 ms 61572 KB Output is correct
26 Correct 1115 ms 63864 KB Output is correct
27 Correct 1101 ms 63844 KB Output is correct
28 Correct 1078 ms 61176 KB Output is correct
29 Correct 1087 ms 61180 KB Output is correct
30 Correct 1080 ms 61176 KB Output is correct