제출 #1277555

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277555		pedreitorzelda	Wall (IOI14_wall)	C++20	24 / 100	367 ms	10596 KiB

wall

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;
struct segTree{
    int sz;
    vector<int>lz_upd_hi;
    vector<int>lz_upd_lo;
    vector<bool>lz_last_hi;
    void init(int n){
        sz = 1;
        while(sz<n)sz*=2;
        lz_upd_hi.resize(sz*2,-1);
        lz_last_hi.resize(sz*2,0);
        lz_upd_lo.resize(sz*2,INF);
    }
    void push(int v){
        if(lz_upd_hi[v]!=-1){
            if(lz_upd_lo[v*2]==INF||(min(lz_upd_lo[v*2],lz_upd_lo[v])>lz_upd_hi[v]))lz_upd_hi[v*2]=max(lz_upd_hi[v*2],lz_upd_hi[v]);
            else lz_upd_hi[v*2]=lz_upd_lo[v*2]=max(lz_upd_hi[v*2],lz_upd_hi[v]);
            lz_last_hi[v*2]=lz_last_hi[v*2+1]=lz_last_hi[v];
            if(lz_upd_lo[v*2+1]==INF||(min(lz_upd_lo[v*2+1],lz_upd_lo[v])>lz_upd_hi[v]))lz_upd_hi[v*2+1]=max(lz_upd_hi[v*2+1],lz_upd_hi[v]);
            else lz_upd_hi[v*2+1]=lz_upd_lo[v*2+1]=max(lz_upd_hi[v*2+1],lz_upd_hi[v]);
            lz_upd_hi[v]=-1;
        }if(lz_upd_lo[v]!=INF){
            if(lz_upd_hi[v*2]==-1||(lz_upd_lo[v]>max(lz_upd_hi[v*2],lz_upd_hi[v])))lz_upd_lo[v*2]=min(lz_upd_lo[v*2],lz_upd_lo[v]);
            else lz_upd_hi[v*2]=lz_upd_lo[v*2]=min(lz_upd_lo[v*2],lz_upd_lo[v]);
            lz_last_hi[v*2]=lz_last_hi[v*2+1]=lz_last_hi[v];
            if(lz_upd_hi[v*2+1]==-1||(lz_upd_lo[v]>max(lz_upd_hi[v*2+1],lz_upd_hi[v])))lz_upd_lo[v*2+1]=min(lz_upd_lo[v*2+1],lz_upd_lo[v]);
            else lz_upd_hi[v*2+1]=lz_upd_lo[v*2+1]=min(lz_upd_lo[v*2+1],lz_upd_lo[v]);
            lz_upd_lo[v]=INF;
        }
        return;
    }
    int query(int l,int r,int v,int pos){
        if(l==r){
            if(lz_upd_lo[v]==INF&&lz_upd_hi[v]==-1)return 0;
            else if(lz_upd_lo[v]==INF)return lz_upd_hi[v];
            else if(lz_upd_hi[v]==-1)return 0;
            else if(lz_last_hi[v])return lz_upd_hi[v];
            else return lz_upd_lo[v];
        }int mid = (l+r)/2;
        push(v);
        if(pos<=mid)return query(l,mid,v*2,pos);
        else return query(mid+1,r,v*2+1,pos);
    }void upd(int l,int r,int tl,int tr,int v,int val,bool is_hi){
        if(r<tl||tr<l){
            return;
        }else if(tl<=l&&r<=tr){
            if(is_hi){
                if(lz_upd_lo[v]!=INF&&lz_upd_lo[v]<val)lz_upd_lo[v]=lz_upd_hi[v]=max(val,lz_upd_hi[v]);
                else lz_upd_hi[v]=max(val,lz_upd_hi[v]);
                lz_last_hi[v]=true;
            }else{
                if(lz_upd_hi[v]!=-1&&lz_upd_hi[v]>val)lz_upd_lo[v]=lz_upd_hi[v]=min(val,lz_upd_lo[v]);
                else lz_upd_lo[v]=min(val,lz_upd_lo[v]);
                lz_last_hi[v]=false;
            }
            return;
        }else{
            int mid = (l+r)/2;
            push(v);
            upd(l,mid,tl,tr,v*2,val,is_hi);
            upd(mid+1,r,tl,tr,v*2+1,val,is_hi);
            return;
        }
    }
};/*
void buildWall(int n, int k, int op[], int left[], int right[],
int height[], int finalHeight[]);*/
void buildWall(int n, int k, int op[], int left[], int right[],
int height[], int finalHeight[]){
    segTree seg;
    seg.init(n+2);
    for(int i=0;i<k;i++){
        if(op[i]==1){
            seg.upd(0,n-1,left[i],right[i],1,height[i],1);
        }else{
            seg.upd(0,n-1,left[i],right[i],1,height[i],0);
        }
        
    }for(int i=0;i<n;i++){
        finalHeight[i]=seg.query(0,n-1,1,i);
    }return;
}/*
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin >> n >> k;
    int op[k],left[k],right[k],height[k],finalHeight[n];
    for(int i=0;i<k;i++){
        cin >> op[i] >> left[i] >> right[i] >> height[i];
    }buildWall(n,k,op,left,right,height,finalHeight);
    for(int i=0;i<n;i++){
        cout << finalHeight[i] << " ";
    }cout << '\n';
    return 0;
}*/
/*
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0

*/

• Subtask 1: 0 / 8
• Subtask 2: 24 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39