oj.uz

Submission #763520

# Submission time Handle Problem Language Result Execution time Memory
763520 2023-06-22T12:07:32 Z Ahmed57 Wall (IOI14_wall) C++17
100 / 100
 598 ms 103900 KB 
#include <bits/stdc++.h>

using namespace std;
int seg[6000001];
void build(int p,int l,int r){
    if(l==r){
        seg[p] = 0;
        return ;
    }
    int md = (l+r)/2;
    build(p*2,l,md);build(p*2+1,md+1,r);
}
int li[6000001],ri[6000001];
void prop(int p,int l,int r){
    if(li[p]==-1)return ;
    //cout<<l<<" "<<r<<" "<<li[p]<<" "<<ri[p]<<endl;
    if(l==r){
        if(seg[p]<li[p]){
            seg[p] = li[p];
        }if(seg[p]>ri[p]){
            seg[p] = ri[p];
        }
    }
    if(l!=r){
        if(li[p*2]==-1){
            li[p*2] = li[p];
            ri[p*2] = ri[p];
        }else{
            if(ri[p*2]<li[p]){
                li[p*2] = li[p];
                ri[p*2] = li[p];
            }else if(ri[p]<li[p*2]){
                li[p*2] = ri[p];
                ri[p*2] = ri[p];
            }else{
                li[p*2] = max(li[p*2],li[p]);
                ri[p*2] = min(ri[p*2],ri[p]);
            }
        }
        if(li[p*2+1]==-1){
            li[p*2+1] = li[p];
            ri[p*2+1] = ri[p];
        }else{
            if(ri[p*2+1]<li[p]){
                li[p*2+1] = li[p];
                ri[p*2+1] = li[p];
            }else if(ri[p]<li[p*2+1]){
                li[p*2+1] = ri[p];
                ri[p*2+1] = ri[p];
            }else{
                li[p*2+1] = max(li[p*2+1],li[p]);
                ri[p*2+1] = min(ri[p*2+1],ri[p]);
            }
        }
    }
    li[p] = -1 , ri[p] = -1;
}
void update(int p,int l,int r,int lq,int rq,int ll,int rr){
    prop(p,l,r);
    if(l>=lq&&r<=rq){
        li[p]=ll;
        ri[p]=rr;
        prop(p,l,r);
        return ;
    }
    if(l>rq||r<lq)return ;
    int md = (l+r)/2;
    update(p*2,l,md,lq,rq,ll,rr);
    update(p*2+1,md+1,r,lq,rq,ll,rr);
}
vector<int> ans;
void dfs(int p,int l,int r){
    prop(p,l,r);
    if(l==r){
        ans.push_back(seg[p]);
        return ;
    }
    int md = (l+r)/2;
    dfs(p*2,l,md);
    dfs(p*2+1,md+1,r);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
    memset(li,-1,sizeof li);
    memset(ri,-1,sizeof ri);
    build(1,1,n);
    for(int i = 0;i<k;i++){
        if(op[i]==1){
            update(1,1,n,left[i]+1,right[i]+1,height[i],1e9);
        }else{
            update(1,1,n,left[i]+1,right[i]+1,0,height[i]);
        }
        ans.clear();
    }
    dfs(1,1,n);
    for(int i = 0;i<n;i++){
        finalHeight[i] = ans[i];
    }
}
/*
int main(){
    int op[] = {1,2,2,1,1,2};
    int height[] = {4,1,5,3,5,0};
    int left[] = {1,4,3,0,2,6};
    int right[] = {8,9,6,5,2,7};
    buildWall(10,6,op,left,right,height);
    return 0;
}
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 47188 KB Output is correct
2 Correct 17 ms 47276 KB Output is correct
3 Correct 20 ms 47232 KB Output is correct
4 Correct 30 ms 47604 KB Output is correct
5 Correct 18 ms 47660 KB Output is correct
6 Correct 27 ms 47652 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 47240 KB Output is correct
2 Correct 152 ms 60820 KB Output is correct
3 Correct 212 ms 54796 KB Output is correct
4 Correct 526 ms 66600 KB Output is correct
5 Correct 265 ms 67560 KB Output is correct
6 Correct 234 ms 66000 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 47188 KB Output is correct
2 Correct 21 ms 47400 KB Output is correct
3 Correct 22 ms 47232 KB Output is correct
4 Correct 31 ms 47644 KB Output is correct
5 Correct 28 ms 47640 KB Output is correct
6 Correct 26 ms 47676 KB Output is correct
7 Correct 18 ms 47204 KB Output is correct
8 Correct 151 ms 60992 KB Output is correct
9 Correct 200 ms 54816 KB Output is correct
10 Correct 562 ms 66552 KB Output is correct
11 Correct 276 ms 67568 KB Output is correct
12 Correct 227 ms 66116 KB Output is correct
13 Correct 20 ms 47260 KB Output is correct
14 Correct 123 ms 60880 KB Output is correct
15 Correct 51 ms 48764 KB Output is correct
16 Correct 598 ms 66812 KB Output is correct
17 Correct 245 ms 66180 KB Output is correct
18 Correct 242 ms 66176 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47144 KB Output is correct
2 Correct 19 ms 47324 KB Output is correct
3 Correct 20 ms 47224 KB Output is correct
4 Correct 24 ms 47700 KB Output is correct
5 Correct 28 ms 47652 KB Output is correct
6 Correct 23 ms 47688 KB Output is correct
7 Correct 19 ms 47260 KB Output is correct
8 Correct 118 ms 60908 KB Output is correct
9 Correct 189 ms 54748 KB Output is correct
10 Correct 531 ms 66624 KB Output is correct
11 Correct 229 ms 67564 KB Output is correct
12 Correct 253 ms 66044 KB Output is correct
13 Correct 17 ms 47216 KB Output is correct
14 Correct 135 ms 60908 KB Output is correct
15 Correct 49 ms 48768 KB Output is correct
16 Correct 595 ms 66760 KB Output is correct
17 Correct 245 ms 66180 KB Output is correct
18 Correct 242 ms 66184 KB Output is correct
19 Correct 549 ms 103856 KB Output is correct
20 Correct 539 ms 101388 KB Output is correct
21 Correct 546 ms 103892 KB Output is correct
22 Correct 535 ms 101328 KB Output is correct
23 Correct 549 ms 101388 KB Output is correct
24 Correct 557 ms 101348 KB Output is correct
25 Correct 533 ms 101400 KB Output is correct
26 Correct 588 ms 103828 KB Output is correct
27 Correct 541 ms 103900 KB Output is correct
28 Correct 532 ms 101452 KB Output is correct
29 Correct 537 ms 101368 KB Output is correct
30 Correct 535 ms 101596 KB Output is correct