oj.uz

Submission #67905

# Submission time Handle Problem Language Result Execution time Memory
67905 2018-08-15T13:02:45 Z edisonhello Wall (IOI14_wall) C++14
61 / 100
 1074 ms 263168 KB 
#include<bits/stdc++.h>
using namespace std;

struct node{
    node *l,*r;
    int mx,mn;
    void addtag(int t,int x){
        if(t==1)mn=max(mn,x),mx=max(mx,mn);
        else    mx=min(mx,x),mn=min(mn,mx);
    }
    void push(){
        if(!l)return;
        l->addtag(1,mn);
        l->addtag(2,mx);
        r->addtag(1,mn);
        r->addtag(2,mx);
        mx=1e9,mn=-1e9;
    }
    node():l(0),r(0),mx(1e9),mn(-1e9){}
} *root;

int *ans;

#define mid ((l+r)>>1)
void build(node *now,int l,int r){
    if(l==r){ return; }
    build(now->l=new node(),l,mid);
    build(now->r=new node(),mid+1,r);
}
void modify(node *now,int l,int r,int ml,int mr,int t,int x){
    if(r<ml || mr<l)return;
    now->push();
    if(ml<=l&&r<=mr){
        now->addtag(t,x);
        return;
    }
    modify(now->l,l,mid,ml,mr,t,x);
    modify(now->r,mid+1,r,ml,mr,t,x);
}
void dfs(node *now,int l,int r,int mn,int mx){
    mn=max(mn,now->mn); mx=max(mx,now->mx);
    now->push();
    if(l==r){
        if(0<now->mn)ans[l]=now->mn;
        else if(0>now->mx)ans[l]=now->mx;
        else ans[l]=0;
        return;
    }
    dfs(now->l,l,mid,mn,mx);
    dfs(now->r,mid+1,r,mn,mx);
}

void buildWall(int n,int q,int types[],int ls[],int rs[],int hs[],int __ans[]){
    ans=__ans;
    build(root=new node(),0,n-1);
    for(int i=0;i<q;++i){
        modify(root,0,n-1,ls[i],rs[i],types[i],hs[i]);
    }
    dfs(root,0,n-1,-1e9,1e9);
}

#ifdef WEAK
int __o[500005],__l[500005],__r[500005],__h[500005],__ans[2000005];
int main(){
    int n; cin>>n;
    int q; cin>>q;
    for(int i=0;i<q;++i)cin>>__o[i]>>__l[i]>>__r[i]>>__h[i];
    buildWall(n,q,__o,__l,__r,__h,__ans);
    for(int i=0;i<n;++i)cout<<__ans[i]<<" ";
    cout<<endl;
}
#endif

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 10 ms 1456 KB Output is correct
5 Correct 9 ms 1572 KB Output is correct
6 Correct 8 ms 1624 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1624 KB Output is correct
2 Correct 216 ms 8768 KB Output is correct
3 Correct 217 ms 8768 KB Output is correct
4 Correct 729 ms 25372 KB Output is correct
5 Correct 348 ms 35952 KB Output is correct
6 Correct 379 ms 44660 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 44660 KB Output is correct
2 Correct 4 ms 44660 KB Output is correct
3 Correct 3 ms 44660 KB Output is correct
4 Correct 9 ms 44660 KB Output is correct
5 Correct 9 ms 44660 KB Output is correct
6 Correct 13 ms 44660 KB Output is correct
7 Correct 3 ms 44660 KB Output is correct
8 Correct 188 ms 44660 KB Output is correct
9 Correct 239 ms 44660 KB Output is correct
10 Correct 669 ms 53944 KB Output is correct
11 Correct 429 ms 64708 KB Output is correct
12 Correct 357 ms 73136 KB Output is correct
13 Correct 2 ms 73136 KB Output is correct
14 Correct 192 ms 73136 KB Output is correct
15 Correct 43 ms 73136 KB Output is correct
16 Correct 659 ms 88892 KB Output is correct
17 Correct 355 ms 97968 KB Output is correct
18 Correct 458 ms 107144 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 107144 KB Output is correct
2 Correct 5 ms 107144 KB Output is correct
3 Correct 4 ms 107144 KB Output is correct
4 Correct 15 ms 107144 KB Output is correct
5 Correct 8 ms 107144 KB Output is correct
6 Correct 8 ms 107144 KB Output is correct
7 Correct 2 ms 107144 KB Output is correct
8 Correct 195 ms 107144 KB Output is correct
9 Correct 208 ms 107144 KB Output is correct
10 Correct 633 ms 116376 KB Output is correct
11 Correct 338 ms 127100 KB Output is correct
12 Correct 344 ms 135796 KB Output is correct
13 Correct 4 ms 135796 KB Output is correct
14 Correct 212 ms 135796 KB Output is correct
15 Correct 37 ms 135796 KB Output is correct
16 Correct 726 ms 151528 KB Output is correct
17 Correct 366 ms 160640 KB Output is correct
18 Correct 392 ms 169532 KB Output is correct
19 Runtime error 1074 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
20 Halted 0 ms 0 KB -