Submission #18408

# Submission time Handle Problem Language Result Execution time Memory
18408 2016-01-31T12:31:11 Z chan492811 Wall (IOI14_wall) C++
100 / 100
1069 ms 141724 KB
#include <algorithm>
#define INF 2100000000
using namespace std;
int n,m,tn=1;
struct data{
    int maxh,minh,l,r;
};
data tree[8000010];
void make_tree(int a){
    if(a>=tn) return;
    make_tree(a*2); make_tree(a*2+1);
    if(tree[a*2].l==0) return;
    if(tree[a*2+1].l==0){ tree[a]=tree[a*2]; return; }
    tree[a].l=tree[a*2].l; tree[a].r=tree[a*2+1].r;
}
void update_node(int flag,int a,int h){
    if(flag==1){
        tree[a].maxh=max(tree[a].maxh,h);
        tree[a].minh=max(tree[a].minh,h);
    }else{
        tree[a].maxh=min(tree[a].maxh,h);
        tree[a].minh=min(tree[a].minh,h);
    }
}
void update(int flag,int a,int l,int r,int h){
    if(tree[a].l==0 || tree[a].r<l || tree[a].l>r) return;
    if(tree[a].l>=l && tree[a].r<=r){
        update_node(flag,a,h);
    }else{
        update_node(1,a*2,tree[a].minh);
        update_node(2,a*2,tree[a].maxh);
        update_node(1,a*2+1,tree[a].minh);
        update_node(2,a*2+1,tree[a].maxh);
        tree[a].maxh=INF; tree[a].minh=0;
        update(flag,a*2,l,r,h); update(flag,a*2+1,l,r,h);
    }
}
void finalupdate(int a){
    if(tree[a].l==0 || a>=tn) return;
    update_node(1,a*2,tree[a].minh);
    update_node(2,a*2,tree[a].maxh);
    update_node(1,a*2+1,tree[a].minh);
    update_node(2,a*2+1,tree[a].maxh);
    tree[a].maxh=INF; tree[a].minh=0;
    finalupdate(a*2); finalupdate(a*2+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    int i;
    while(tn<n)tn*=2;
    for(i=tn;i<tn+n;i++) tree[i].l=i-tn+1,tree[i].r=i-tn+1;
    make_tree(1);
    for(i=0;i<k;i++){
        update(op[i],1,left[i]+1,right[i]+1,height[i]);
    }
    finalupdate(1);
    for(i=tn;i<tn+n;i++) finalHeight[i-tn]=tree[i].maxh;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 126084 KB Output is correct
2 Correct 0 ms 126084 KB Output is correct
3 Correct 0 ms 126084 KB Output is correct
4 Correct 7 ms 126084 KB Output is correct
5 Correct 8 ms 126084 KB Output is correct
6 Correct 6 ms 126084 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 126084 KB Output is correct
2 Correct 170 ms 133908 KB Output is correct
3 Correct 240 ms 129332 KB Output is correct
4 Correct 617 ms 134300 KB Output is correct
5 Correct 457 ms 134300 KB Output is correct
6 Correct 442 ms 134300 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 126084 KB Output is correct
2 Correct 0 ms 126084 KB Output is correct
3 Correct 0 ms 126084 KB Output is correct
4 Correct 7 ms 126084 KB Output is correct
5 Correct 7 ms 126084 KB Output is correct
6 Correct 6 ms 126084 KB Output is correct
7 Correct 0 ms 126084 KB Output is correct
8 Correct 169 ms 133908 KB Output is correct
9 Correct 248 ms 129332 KB Output is correct
10 Correct 785 ms 134300 KB Output is correct
11 Correct 451 ms 134300 KB Output is correct
12 Correct 478 ms 134300 KB Output is correct
13 Correct 0 ms 126084 KB Output is correct
14 Correct 126 ms 133908 KB Output is correct
15 Correct 43 ms 126568 KB Output is correct
16 Correct 737 ms 134300 KB Output is correct
17 Correct 444 ms 134300 KB Output is correct
18 Correct 479 ms 134300 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 126084 KB Output is correct
2 Correct 0 ms 126084 KB Output is correct
3 Correct 0 ms 126084 KB Output is correct
4 Correct 4 ms 126084 KB Output is correct
5 Correct 6 ms 126084 KB Output is correct
6 Correct 3 ms 126084 KB Output is correct
7 Correct 0 ms 126084 KB Output is correct
8 Correct 175 ms 133908 KB Output is correct
9 Correct 255 ms 129332 KB Output is correct
10 Correct 732 ms 134300 KB Output is correct
11 Correct 508 ms 134300 KB Output is correct
12 Correct 466 ms 134300 KB Output is correct
13 Correct 0 ms 126084 KB Output is correct
14 Correct 169 ms 133908 KB Output is correct
15 Correct 43 ms 126568 KB Output is correct
16 Correct 745 ms 134300 KB Output is correct
17 Correct 413 ms 134300 KB Output is correct
18 Correct 485 ms 134300 KB Output is correct
19 Correct 1047 ms 141724 KB Output is correct
20 Correct 992 ms 141724 KB Output is correct
21 Correct 1000 ms 141724 KB Output is correct
22 Correct 1011 ms 141724 KB Output is correct
23 Correct 1007 ms 141724 KB Output is correct
24 Correct 964 ms 141724 KB Output is correct
25 Correct 854 ms 141724 KB Output is correct
26 Correct 981 ms 141724 KB Output is correct
27 Correct 1005 ms 141724 KB Output is correct
28 Correct 1017 ms 141724 KB Output is correct
29 Correct 1069 ms 141724 KB Output is correct
30 Correct 851 ms 141724 KB Output is correct