Submission #520784

#	Time	Username	Problem	Language	Result	Execution time	Memory
520784		krit3379	Wall (IOI14_wall)	C++17	100 / 100	598 ms	86016 KiB

wall

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

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

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

void push(int x){
    if(t[x].mi!=-1){
        int xl=x*2,xr=xl+1,mi=t[x].mi,ma=t[x].ma;
        if(t[x].exact!=-1)t[xl]=t[xr]=t[x];
        else{
            if(t[xl].mi==-1)t[xl]=t[x];
            else 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(t[xl].mi==mi)t[xl].exact=mi;
                    else t[xl].exact=ma;
                }
            }
            else{
                if(t[xl].exact<mi)t[xl].exact=mi;
                else if(t[xl].exact>ma)t[xl].exact=ma;
            }
            if(t[xr].mi==-1)t[xr]=t[x];
            else 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(t[xr].mi==mi)t[xr].exact=mi;
                    else t[xr].exact=ma;
                }
            }
            else{
                if(t[xr].exact<mi)t[xr].exact=mi;
                else if(t[xr].exact>ma)t[xr].exact=ma;
            }
        }
        t[x].mi=-1;
    }
}

void cre(int x,int l,int r){
    if(l==r)return ;
    t[x]={-1,-1,-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].mi!=-1){
            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(t[x].mi==mi)t[x].exact=mi;
                    else t[x].exact=ma;
                }
            }
            else{
                if(t[x].exact<mi)t[x].exact=mi;
                else if(t[x].exact>ma)t[x].exact=ma;
            }
        }
        else t[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-1]=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]+1;
        rr=right[i]+1;
        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: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39