oj.uz

Submission #67909

# Submission time Handle Problem Language Result Execution time Memory
67909 2018-08-15T13:26:42 Z edisonhello Wall (IOI14_wall) C++14
100 / 100
 1335 ms 164040 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,pool[6000001]; */
int lc[6000001],rc[6000001],mx[6000001],mn[6000001],ptr=0;

void addtag(int now,int t,int x){
    if(t==1)mn[now]=max(mn[now],x),mx[now]=max(mx[now],mn[now]);
    else    mx[now]=min(mx[now],x),mn[now]=min(mn[now],mx[now]);
}
void push(int now){
    if(!lc[now])return;
    addtag(lc[now],1,mn[now]);
    addtag(lc[now],2,mx[now]);
    addtag(rc[now],1,mn[now]);
    addtag(rc[now],2,mx[now]);
    mn[now]=0,mx[now]=0x3f3f3f3f;
}

int *ans;

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

void buildWall(int n,int q,int types[],int ls[],int rs[],int hs[],int __ans[]){
    memset(mx,0x3f,sizeof(mx));

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

#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 24 ms 23800 KB Output is correct
2 Correct 27 ms 24128 KB Output is correct
3 Correct 25 ms 24128 KB Output is correct
4 Correct 30 ms 24588 KB Output is correct
5 Correct 32 ms 24624 KB Output is correct
6 Correct 37 ms 24776 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24776 KB Output is correct
2 Correct 228 ms 32320 KB Output is correct
3 Correct 340 ms 32320 KB Output is correct
4 Correct 925 ms 41880 KB Output is correct
5 Correct 484 ms 42336 KB Output is correct
6 Correct 394 ms 42336 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 42336 KB Output is correct
2 Correct 23 ms 42336 KB Output is correct
3 Correct 27 ms 42336 KB Output is correct
4 Correct 28 ms 42336 KB Output is correct
5 Correct 32 ms 42336 KB Output is correct
6 Correct 28 ms 42336 KB Output is correct
7 Correct 20 ms 42336 KB Output is correct
8 Correct 221 ms 42336 KB Output is correct
9 Correct 273 ms 42336 KB Output is correct
10 Correct 941 ms 42336 KB Output is correct
11 Correct 451 ms 42336 KB Output is correct
12 Correct 431 ms 42336 KB Output is correct
13 Correct 21 ms 42336 KB Output is correct
14 Correct 213 ms 42336 KB Output is correct
15 Correct 67 ms 42336 KB Output is correct
16 Correct 883 ms 42336 KB Output is correct
17 Correct 520 ms 42336 KB Output is correct
18 Correct 459 ms 42336 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42336 KB Output is correct
2 Correct 25 ms 42336 KB Output is correct
3 Correct 24 ms 42336 KB Output is correct
4 Correct 33 ms 42336 KB Output is correct
5 Correct 27 ms 42336 KB Output is correct
6 Correct 36 ms 42336 KB Output is correct
7 Correct 21 ms 42336 KB Output is correct
8 Correct 228 ms 42336 KB Output is correct
9 Correct 302 ms 42336 KB Output is correct
10 Correct 871 ms 42336 KB Output is correct
11 Correct 421 ms 42336 KB Output is correct
12 Correct 441 ms 42508 KB Output is correct
13 Correct 22 ms 42508 KB Output is correct
14 Correct 215 ms 42508 KB Output is correct
15 Correct 63 ms 42508 KB Output is correct
16 Correct 938 ms 42508 KB Output is correct
17 Correct 458 ms 42508 KB Output is correct
18 Correct 416 ms 42508 KB Output is correct
19 Correct 1335 ms 103952 KB Output is correct
20 Correct 1177 ms 103952 KB Output is correct
21 Correct 1294 ms 103952 KB Output is correct
22 Correct 1123 ms 103952 KB Output is correct
23 Correct 1142 ms 103952 KB Output is correct
24 Correct 1031 ms 103952 KB Output is correct
25 Correct 1117 ms 111740 KB Output is correct
26 Correct 1035 ms 124732 KB Output is correct
27 Correct 1055 ms 135212 KB Output is correct
28 Correct 1016 ms 143248 KB Output is correct
29 Correct 1038 ms 153580 KB Output is correct
30 Correct 1082 ms 164040 KB Output is correct