oj.uz

Submission #597636

# Submission time Handle Problem Language Result Execution time Memory
597636 2022-07-16T12:50:09 Z enerelt14 Wall (IOI14_wall) C++14
100 / 100
 786 ms 128020 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
struct node{
    int lazy, mn, mx;
    node(){
        lazy=-1;
        mn=0;
        mx=0;
    }
};
node tree[8000005];
void propagate(int id, int l, int r){
    if (l==r)return;
    if (tree[id].lazy!=-1){
        tree[id*2+1].lazy=tree[id].lazy;
        tree[id*2+2].lazy=tree[id].lazy;
        tree[id*2+1].mn=tree[id].lazy;
        tree[id*2+2].mn=tree[id].lazy;
        tree[id*2+1].mx=tree[id].lazy;
        tree[id*2+2].mx=tree[id].lazy;
    }
    tree[id].mn=min(tree[id*2+1].mn, tree[id*2+2].mn);
    tree[id].mx=max(tree[id*2+1].mx, tree[id*2+2].mx);
    tree[id].lazy=-1;
}
void update(int x, int id, int l, int r, int L, int R, int h){
    if (l>R || L>r)return;
    if (!x && tree[id].mn>=h)return;
    if (x && tree[id].mx<=h)return;
    if (L<=l && r<=R && tree[id].mn==tree[id].mx){
        if (x){
            if (tree[id].lazy==-1)tree[id].lazy=h;
            else tree[id].lazy=min(tree[id].lazy, h);
            tree[id].mx=min(tree[id].mx, h);
            tree[id].mn=min(tree[id].mn, h);
        }
        else{
            tree[id].lazy=max(tree[id].lazy, h);
            tree[id].mx=max(tree[id].mx, h);
            tree[id].mn=max(tree[id].mn, h);
        }
        return;
    }
    propagate(id, l, r);
    int mid=(l+r)/2;
    update(x, id*2+1, l, mid, L, R, h);
    update(x, id*2+2, mid+1, r, L, R, h);
    tree[id].mn=min(tree[id*2+1].mn, tree[id*2+2].mn);
    tree[id].mx=max(tree[id*2+1].mx, tree[id*2+2].mx);
}
int x[2000005];
void build(int id, int l, int r){
    propagate(id, l, r);
    if (l==r){
        x[l]=tree[id].mn;
        return;
    }
    int mid=(l+r)/2;
    build(id*2+1, l, mid);
    build(id*2+2, mid+1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i=0;i<k;i++){
        update(op[i]-1, 0, 0, n-1, left[i], right[i], height[i]);
    }
    build(0, 0, n-1);
    for (int i=0;i<n;i++)finalHeight[i]=x[i];
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 94116 KB Output is correct
2 Correct 45 ms 94276 KB Output is correct
3 Correct 42 ms 94168 KB Output is correct
4 Correct 49 ms 94412 KB Output is correct
5 Correct 47 ms 94416 KB Output is correct
6 Correct 48 ms 94412 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 94156 KB Output is correct
2 Correct 176 ms 102072 KB Output is correct
3 Correct 108 ms 97688 KB Output is correct
4 Correct 196 ms 103064 KB Output is correct
5 Correct 236 ms 103628 KB Output is correct
6 Correct 237 ms 103572 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 94136 KB Output is correct
2 Correct 53 ms 94196 KB Output is correct
3 Correct 52 ms 94140 KB Output is correct
4 Correct 49 ms 94408 KB Output is correct
5 Correct 46 ms 94412 KB Output is correct
6 Correct 46 ms 94312 KB Output is correct
7 Correct 42 ms 94160 KB Output is correct
8 Correct 185 ms 101964 KB Output is correct
9 Correct 113 ms 97636 KB Output is correct
10 Correct 206 ms 103100 KB Output is correct
11 Correct 257 ms 103552 KB Output is correct
12 Correct 235 ms 103576 KB Output is correct
13 Correct 42 ms 94124 KB Output is correct
14 Correct 178 ms 102048 KB Output is correct
15 Correct 78 ms 94844 KB Output is correct
16 Correct 607 ms 103264 KB Output is correct
17 Correct 347 ms 103252 KB Output is correct
18 Correct 349 ms 103264 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 94192 KB Output is correct
2 Correct 43 ms 94268 KB Output is correct
3 Correct 44 ms 94152 KB Output is correct
4 Correct 54 ms 94412 KB Output is correct
5 Correct 55 ms 94336 KB Output is correct
6 Correct 58 ms 94420 KB Output is correct
7 Correct 45 ms 94164 KB Output is correct
8 Correct 181 ms 101968 KB Output is correct
9 Correct 117 ms 97660 KB Output is correct
10 Correct 226 ms 102992 KB Output is correct
11 Correct 212 ms 103600 KB Output is correct
12 Correct 238 ms 103508 KB Output is correct
13 Correct 41 ms 94132 KB Output is correct
14 Correct 170 ms 101964 KB Output is correct
15 Correct 74 ms 94860 KB Output is correct
16 Correct 614 ms 103292 KB Output is correct
17 Correct 342 ms 103256 KB Output is correct
18 Correct 337 ms 103292 KB Output is correct
19 Correct 724 ms 128008 KB Output is correct
20 Correct 728 ms 125584 KB Output is correct
21 Correct 786 ms 128016 KB Output is correct
22 Correct 723 ms 125616 KB Output is correct
23 Correct 744 ms 125516 KB Output is correct
24 Correct 738 ms 125564 KB Output is correct
25 Correct 744 ms 125428 KB Output is correct
26 Correct 735 ms 128020 KB Output is correct
27 Correct 736 ms 127976 KB Output is correct
28 Correct 708 ms 125412 KB Output is correct
29 Correct 719 ms 125504 KB Output is correct
30 Correct 747 ms 125500 KB Output is correct