oj.uz

Submission #441697

# Submission time Handle Problem Language Result Execution time Memory
441697 2021-07-05T20:33:42 Z julian33 Wall (IOI14_wall) C++14
100 / 100
 788 ms 110376 KB 
#include <bits/stdc++.h>

using namespace std;

void scan(){}
template<typename F, typename... R> void scan(F &f,R&... r){cin>>f;scan(r...);}

#define rng(x) x.begin(),x.end()
#define FOR(i,j,n) for(int i=j;i<n;i++)
#define read(v,n) for(int i=0;i<n;i++) scan(v[i])
#define fill(x) memset(x,0,sizeof(x))
#define IOS ios_base::sync_with_stdio(false),cin.tie(NULL)
#define MAXN numeric_limits<int>::max()
#define MAXLN numeric_limits<long long int>::max()
#define MAXD numeric_limits<double>::max()
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef pair<string,int> psi;
typedef pair<string,double> psd;
typedef unordered_set<int> usi;
typedef multiset<int> msi;
typedef unordered_map<int,int> umii;
typedef double db;
typedef long double ldb;

const int mx=2e6+1;

struct node{
    int flr,cl,def;
    bool lazy;
};

node st[4*mx];

void push(int v){
    if(!st[v].lazy) return;
    if(st[v].def!=-1){
        st[v<<1].def=st[v<<1|1].def=st[v].def;
        st[v<<1].flr=st[v<<1|1].flr=0;
        st[v<<1|1].cl=st[v<<1|1].cl=MAXN;
    } else{
        if(st[v<<1].def!=-1){
            st[v<<1].def=max(st[v<<1].def,st[v].flr);
            st[v<<1].def=min(st[v<<1].def,st[v].cl);
        }
        else if(st[v].flr>=st[v<<1].cl){
            st[v<<1].cl=MAXN;
            st[v<<1].flr=0;
            st[v<<1].def=st[v].flr;
        } else if(st[v].cl<=st[v<<1].flr){
            st[v<<1].cl=MAXN;
            st[v<<1].flr=0;
            st[v<<1].def=st[v].cl;
        } else{
            st[v<<1].cl=min(st[v<<1].cl,st[v].cl);
            st[v<<1].flr=max(st[v<<1].flr,st[v].flr);
        }
        if(st[v<<1|1].def!=-1){
            st[v<<1|1].def=max(st[v<<1|1].def,st[v].flr);
            st[v<<1|1].def=min(st[v<<1|1].def,st[v].cl);
        }
        else if(st[v].flr>=st[v<<1|1].cl){
            st[v<<1|1].cl=MAXN;
            st[v<<1|1].flr=0;
            st[v<<1|1].def=st[v].flr;
        } else if(st[v].cl<=st[v<<1|1].flr){
            st[v<<1|1].cl=MAXN;
            st[v<<1|1].flr=0;
            st[v<<1|1].def=st[v].cl;
        } else{
            st[v<<1|1].cl=min(st[v<<1|1].cl,st[v].cl);
            st[v<<1|1].flr=max(st[v<<1|1].flr,st[v].flr);
        }
    }
    st[v].lazy=false;
    st[v].flr=0; st[v].cl=MAXN; st[v].def=-1;
    st[v<<1].lazy=st[v<<1|1].lazy=true;
}

void build(int v,int l,int r){
    if(l==r) st[v]=(node){0,MAXN,0,0};
    else{
        int m=(l+r)>>1;
        build(v<<1,l,m);
        build(v<<1|1,m+1,r);
        st[v]=(node){0,MAXN,-1,0};
    }
}

void update(int v,int l,int r,int lq,int rq,int op,int val){
    if(l<r) push(v);
    if(lq>rq) return;
    if(l>=lq&&r<=rq){
        st[v].lazy=true;
        if(op==1){
            if(st[v].cl<=val){
                st[v].cl=MAXN;
                st[v].flr=0;
                st[v].def=val;
            } else if(st[v].def!=-1) st[v].def=max(st[v].def,val);
            else st[v].flr=max(st[v].flr,val);
        } else{
            if(st[v].flr>=val){
                st[v].flr=0;
                st[v].cl=MAXN;
                st[v].def=val;
            } else if(st[v].def!=-1) st[v].def=min(st[v].def,val);
            else st[v].cl=min(st[v].cl,val);
        }
//        cout<<l<<"->"<<r<<": "<<st[v].flr<<"->"<<st[v].cl<<" "<<st[v].def<<"\n";
        if(l<r) push(v);
    } else{
        int m=(l+r)>>1;
//        cout<<l<<"->"<<r<<": "<<st[v].flr<<"->"<<st[v].cl<<" "<<st[v].def<<"\n";
        update(v<<1,l,m,lq,min(m,rq),op,val);
        update(v<<1|1,m+1,r,max(lq,m+1),rq,op,val);
    }
}

vector<int> ans;

void print(int v,int l,int r){
//    cout<<l<<"->"<<r<<": "<<st[v].flr<<"->"<<st[v].cl<<" "<<st[v].def<<"\n";
//    if(l==4&&r==5){
//        cout<<st[v<<1|1].flr<<" "<<st[v<<1|1].cl<<" "<<st[v<<1|1].def<<"\n";
//    }
    if(l==r) ans.push_back(st[v].def);
    else{
        push(v);
        int m=(l+r)>>1;
        print(v<<1,l,m);
        print(v<<1|1,m+1,r);
    }
}

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
    build(1,1,n);
    for(int i=0;i<k;i++){
        left[i]++; right[i]++;
        update(1,1,n,left[i],right[i],op[i],height[i]);
    }
    print(1,1,n);
    for(int i=0;i<n;i++)
        finalHeight[i]=ans[i];
}

Compilation message

wall.cpp: In function 'void push(int)':
wall.cpp:44:22: warning: operation on 'st[((v << 1) | 1)].node::cl' may be undefined [-Wsequence-point]
   44 |         st[v<<1|1].cl=st[v<<1|1].cl=MAXN;
      |                      ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 8 ms 1140 KB Output is correct
5 Correct 5 ms 1140 KB Output is correct
6 Correct 5 ms 1184 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 165 ms 13892 KB Output is correct
3 Correct 271 ms 8660 KB Output is correct
4 Correct 750 ms 22972 KB Output is correct
5 Correct 294 ms 23980 KB Output is correct
6 Correct 289 ms 22368 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 1144 KB Output is correct
5 Correct 5 ms 1100 KB Output is correct
6 Correct 5 ms 1100 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 164 ms 13872 KB Output is correct
9 Correct 252 ms 8680 KB Output is correct
10 Correct 734 ms 22980 KB Output is correct
11 Correct 306 ms 24012 KB Output is correct
12 Correct 287 ms 22372 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 163 ms 13896 KB Output is correct
15 Correct 45 ms 2752 KB Output is correct
16 Correct 676 ms 23132 KB Output is correct
17 Correct 292 ms 22800 KB Output is correct
18 Correct 289 ms 22608 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 9 ms 1132 KB Output is correct
5 Correct 6 ms 1100 KB Output is correct
6 Correct 5 ms 1100 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 163 ms 13948 KB Output is correct
9 Correct 265 ms 8632 KB Output is correct
10 Correct 746 ms 22968 KB Output is correct
11 Correct 295 ms 23916 KB Output is correct
12 Correct 287 ms 22376 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 163 ms 13888 KB Output is correct
15 Correct 39 ms 2636 KB Output is correct
16 Correct 734 ms 23312 KB Output is correct
17 Correct 296 ms 22588 KB Output is correct
18 Correct 295 ms 22584 KB Output is correct
19 Correct 783 ms 110204 KB Output is correct
20 Correct 773 ms 107808 KB Output is correct
21 Correct 771 ms 110284 KB Output is correct
22 Correct 759 ms 107784 KB Output is correct
23 Correct 770 ms 107812 KB Output is correct
24 Correct 779 ms 107892 KB Output is correct
25 Correct 776 ms 107804 KB Output is correct
26 Correct 780 ms 110236 KB Output is correct
27 Correct 788 ms 110376 KB Output is correct
28 Correct 788 ms 107944 KB Output is correct
29 Correct 774 ms 107920 KB Output is correct
30 Correct 777 ms 107888 KB Output is correct