oj.uz

Submission #333483

# Submission time Handle Problem Language Result Execution time Memory
333483 2020-12-06T08:41:35 Z wildturtle Wall (IOI14_wall) C++14
100 / 100
 928 ms 99512 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
vector < pair < int, int > > tree;
void apply(int node,int L,int R) {
    tree[node].first=max(min(tree[node].first,R),L);
    tree[node].second=max(min(tree[node].second,R),L);
}
void push(int node,int le,int ri) {
    if(le<ri) {
        apply(2*node,tree[node].first,tree[node].second);
        apply(2*node+1,tree[node].first,tree[node].second);
    }
    tree[node].second=1e9+3;
    tree[node].first=0;
}
void go(int node,int le,int ri,int finalHeight[]) {
    if(le==ri) { finalHeight[le-1]=tree[node].first; return; }
    push(node,le,ri);
    go(2*node,le,(le+ri)/2,finalHeight);
    go(2*node+1,(le+ri)/2+1,ri,finalHeight);
}
void update(int node,int le,int ri,int start,int end,int cur1,int cur2) {
    if(ri<start || le>end) return;
    if(start<=le && ri<=end) { apply(node,cur1,cur2); return; }
    push(node,le,ri);
    update(2*node,le,(le+ri)/2,start,end,cur1,cur2);
    update(2*node+1,(le+ri)/2+1,ri,start,end,cur1,cur2);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]) {
	tree.resize(n*4+1, {0, 1e9});
    for(int i=0;i<k;i++) {
        if(op[i]==1) update(1,1,n,left[i]+1,right[i]+1,height[i],1e9+5);
        else update(1,1,n,left[i]+1,right[i]+1,-(1e9+5),height[i]);
    }
    go(1,1,n,finalHeight);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 6 ms 876 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 6 ms 876 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 156 ms 14016 KB Output is correct
3 Correct 196 ms 8044 KB Output is correct
4 Correct 577 ms 21484 KB Output is correct
5 Correct 365 ms 22764 KB Output is correct
6 Correct 355 ms 20972 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 7 ms 876 KB Output is correct
5 Correct 6 ms 876 KB Output is correct
6 Correct 7 ms 876 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 160 ms 13932 KB Output is correct
9 Correct 199 ms 8044 KB Output is correct
10 Correct 573 ms 21484 KB Output is correct
11 Correct 366 ms 22508 KB Output is correct
12 Correct 347 ms 20972 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 166 ms 13932 KB Output is correct
15 Correct 32 ms 2156 KB Output is correct
16 Correct 568 ms 21792 KB Output is correct
17 Correct 356 ms 21228 KB Output is correct
18 Correct 360 ms 21228 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 6 ms 876 KB Output is correct
5 Correct 6 ms 876 KB Output is correct
6 Correct 6 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 159 ms 13932 KB Output is correct
9 Correct 193 ms 8044 KB Output is correct
10 Correct 563 ms 21484 KB Output is correct
11 Correct 362 ms 22636 KB Output is correct
12 Correct 356 ms 21100 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 160 ms 13932 KB Output is correct
15 Correct 31 ms 2028 KB Output is correct
16 Correct 562 ms 21740 KB Output is correct
17 Correct 358 ms 21268 KB Output is correct
18 Correct 362 ms 21228 KB Output is correct
19 Correct 892 ms 99436 KB Output is correct
20 Correct 885 ms 97016 KB Output is correct
21 Correct 882 ms 99436 KB Output is correct
22 Correct 872 ms 97004 KB Output is correct
23 Correct 885 ms 96876 KB Output is correct
24 Correct 928 ms 96816 KB Output is correct
25 Correct 895 ms 96876 KB Output is correct
26 Correct 886 ms 99436 KB Output is correct
27 Correct 888 ms 99512 KB Output is correct
28 Correct 878 ms 96876 KB Output is correct
29 Correct 876 ms 96876 KB Output is correct
30 Correct 872 ms 96876 KB Output is correct