oj.uz

Submission #151809

# Submission time Handle Problem Language Result Execution time Memory
151809 2019-09-04T23:35:56 Z yum Wall (IOI14_wall) C++14
100 / 100
 1398 ms 69748 KB 
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int,int> pi;
 
int* res;
 
struct segtree{
    pi tree[4200000];
    void upload(int op, int p, int v){
        if(op == 1){
            tree[p].first = max(tree[p].first,v);
            tree[p].second = max(tree[p].second,v);
        }
        else{
            tree[p].first = min(tree[p].first,v);
            tree[p].second = min(tree[p].second,v);
        }
    }
    void insert(int s, int e, int p, int ps, int pe, int v, int op){
        if(pe < s || e < ps) return;
        if(s <= ps && pe <= e){
            upload(op,p,v);
            res[s] = tree[p].first;
        }
        else{
            upload(1,2*p,tree[p].first);
            upload(2,2*p,tree[p].second);
            upload(1,2*p+1,tree[p].first);
            upload(2,2*p+1,tree[p].second);
            tree[p].first = 0;
            tree[p].second = 1e5 + 5;
            int pm = (ps+pe)/2;
            insert(s,e,2*p,ps,pm,v,op);
            insert(s,e,2*p+1,pm+1,pe,v,op);
        }
    }
}seg;
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    res = finalHeight;
    for (int i=0; i<k; i++) {
        seg.insert(left[i],right[i],1,0,n-1,height[i],op[i]);
    }
    for (int i=0; i<n; i++) {
        seg.insert(i,i,1,0,n-1,0,1);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 276 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 10 ms 760 KB Output is correct
5 Correct 9 ms 764 KB Output is correct
6 Correct 9 ms 760 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 180 ms 14040 KB Output is correct
3 Correct 216 ms 8008 KB Output is correct
4 Correct 633 ms 20472 KB Output is correct
5 Correct 366 ms 21468 KB Output is correct
6 Correct 356 ms 19992 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 380 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 10 ms 760 KB Output is correct
5 Correct 9 ms 760 KB Output is correct
6 Correct 9 ms 828 KB Output is correct
7 Correct 2 ms 252 KB Output is correct
8 Correct 178 ms 13904 KB Output is correct
9 Correct 216 ms 7976 KB Output is correct
10 Correct 637 ms 20360 KB Output is correct
11 Correct 371 ms 21564 KB Output is correct
12 Correct 352 ms 19836 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 182 ms 13904 KB Output is correct
15 Correct 39 ms 2168 KB Output is correct
16 Correct 628 ms 20696 KB Output is correct
17 Correct 361 ms 20120 KB Output is correct
18 Correct 357 ms 20116 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 4 ms 508 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 10 ms 760 KB Output is correct
5 Correct 9 ms 760 KB Output is correct
6 Correct 9 ms 888 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 179 ms 14004 KB Output is correct
9 Correct 221 ms 8060 KB Output is correct
10 Correct 630 ms 20368 KB Output is correct
11 Correct 367 ms 21496 KB Output is correct
12 Correct 354 ms 19832 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 183 ms 14056 KB Output is correct
15 Correct 39 ms 2044 KB Output is correct
16 Correct 655 ms 20636 KB Output is correct
17 Correct 359 ms 20216 KB Output is correct
18 Correct 355 ms 20088 KB Output is correct
19 Correct 1382 ms 69748 KB Output is correct
20 Correct 1376 ms 67052 KB Output is correct
21 Correct 1381 ms 69620 KB Output is correct
22 Correct 1373 ms 67164 KB Output is correct
23 Correct 1375 ms 67136 KB Output is correct
24 Correct 1371 ms 67092 KB Output is correct
25 Correct 1398 ms 67056 KB Output is correct
26 Correct 1381 ms 69552 KB Output is correct
27 Correct 1385 ms 69544 KB Output is correct
28 Correct 1369 ms 67072 KB Output is correct
29 Correct 1378 ms 67016 KB Output is correct
30 Correct 1370 ms 67088 KB Output is correct