제출 #441697

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
441697		julian33	벽 (IOI14_wall)	C++14	100 / 100	788 ms	110376 KiB

wall

#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];
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39