제출 #520763

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
520763		krit3379	벽 (IOI14_wall)	C++17	0 / 100	1 ms	332 KiB

wall

#include<bits/stdc++.h>
using namespace std;
#define N 2000005

struct A{
    int mi,ma,exact;
};

A t[4*N],lazy[4*N];
int ll,rr,ma,mi;

void push(int x){
    if(lazy[x].mi!=-1){
        int xl=x*2,xr=xl+1,mi=lazy[x].mi,ma=lazy[x].ma;
        if(lazy[x].exact!=-1)lazy[xl]=lazy[xr]=lazy[x];
        else{
            if(lazy[xl].mi==-1)lazy[xl]=lazy[x];
            else if(lazy[xl].exact==-1){
                lazy[xl].ma=min(lazy[xl].ma,ma);
                lazy[xl].mi=max(lazy[xl].mi,mi);
                if(lazy[xl].mi>lazy[xl].ma){
                    if(mi==0)lazy[xl].exact=ma;
                    else lazy[xl].exact=mi;
                }
            }
            else{
                if(lazy[xl].exact<mi)lazy[xl].exact=mi;
                else if(lazy[xl].exact>ma)lazy[xl].exact=ma;
            }
            if(lazy[xr].mi==-1)lazy[xr]=lazy[x];
            else if(lazy[xr].exact==-1){
                lazy[xr].ma=min(lazy[xr].ma,ma);
                lazy[xr].mi=max(lazy[xr].mi,mi);
                if(lazy[xr].mi>lazy[xr].ma){
                    if(mi==0)lazy[xr].exact=ma;
                    else lazy[xr].exact=mi;
                }
            }
            else{
                if(lazy[xl].exact<mi)lazy[xl].exact=mi;
                else if(lazy[xl].exact>ma)lazy[xl].exact=ma;
            }
        }
        if(t[xl].exact==-1){
            t[xl].ma=min(t[xl].ma,ma);
            t[xl].mi=max(t[xl].mi,mi);
            if(t[xl].mi>t[xl].ma){
                if(mi==0)t[xl].exact=ma;
                else t[xl].exact=mi;
            }
        }
        else{
            if(t[xl].exact<mi)t[xl].exact=mi;
            else if(t[xl].exact>ma)t[xl].exact=ma;
        }
        if(t[xr].exact==-1){
            t[xr].ma=min(t[xr].ma,ma);
            t[xr].mi=max(t[xr].mi,mi);
            if(t[xr].mi>t[xr].ma){
                if(mi==0)t[xr].exact=ma;
                else t[xr].exact=mi;
            }
        }
        else{
            if(t[xr].exact<mi)t[xr].exact=mi;
            else if(t[xr].exact>ma)t[xr].exact=ma;
        }
        lazy[x].mi=-1;
    }
}

void cre(int x,int l,int r){
    if(l==r)return ;
    t[x].exact=-1;
    lazy[x].mi=-1;
    int mid=(l+r)/2;
    cre(x*2,l,mid);
    cre(x*2+1,mid+1,r);
}

void update(int x,int l,int r){
    if(r<ll||rr<l)return ;
    if(ll<=l&&r<=rr){
        if(t[x].exact==-1){
            t[x].ma=min(t[x].ma,ma);
            t[x].mi=max(t[x].mi,mi);
            if(t[x].mi>t[x].ma){
                if(mi==0)t[x].exact=ma;
                else t[x].exact=mi;
            }
        }
        else{
            if(t[x].exact<mi)t[x].exact=mi;
            else if(t[x].exact>ma)t[x].exact=ma;
        }
        if(lazy[x].mi!=-1){
            if(lazy[x].exact==-1){
                lazy[x].ma=min(lazy[x].ma,ma);
                lazy[x].mi=max(lazy[x].mi,mi);
                if(lazy[x].mi>lazy[x].ma){
                    if(mi==0)lazy[x].exact=ma;
                    else lazy[x].exact=mi;
                }
            }
            else{
                if(lazy[x].exact<mi)lazy[x].exact=mi;
                else if(lazy[x].exact>ma)lazy[x].exact=ma;
            }
        }
        else lazy[x]={mi,ma,-1};
        return ;
    }
    push(x);
    int mid=(l+r)/2;
    update(x*2,l,mid);
    update(x*2+1,mid+1,r);
}

void sol(int x,int l,int r,int *ans){
    if(l==r){ans[l]=t[x].exact;return ;}
    push(x);
    int mid=(l+r)/2;
    sol(x*2,l,mid,ans);
    sol(x*2+1,mid+1,r,ans);
}

void buildWall(int n, int k, int *op, int *left, int *right, int *height, int *finalHeight){
    int i,h;
    cre(1,1,n);
    for(i=0;i<k;i++){
        ll=left[i];
        rr=right[i];
        h=height[i];
        if(op[i]==1)mi=h,ma=100000;
        else mi=0,ma=h;
        update(1,1,n);
    }
    sol(1,1,n,finalHeight);
}

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