Submission #827444

#	Time	Username	Problem	Language	Result	Execution time	Memory
827444		bachhoangxuan	Wall (IOI14_wall)	C++17	100 / 100	505 ms	77388 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+5;

int Max[4*maxn],Min[4*maxn],res[maxn];
void pull(int id){
    Max[id]=max(Max[id<<1],Max[id<<1|1]);
    Min[id]=min(Min[id<<1],Min[id<<1|1]);
}
void getnew(int id,int val){
    Max[id]=Min[id]=val;
}
void pushdown(int id){
    if(Min[id]!=Max[id]) return;
    getnew(id<<1,Min[id]);
    getnew(id<<1|1,Min[id]);
}
void update_Max(int l,int r,int id,int tl,int tr,int x){
    if(x<=Min[id] || tr<l || r<tl) return;
    if(tl<=l && r<=tr && x>=Max[id]){
        getnew(id,x);
        return;
    }
    pushdown(id);
    int mid=(l+r)>>1;
    update_Max(l,mid,id<<1,tl,tr,x);update_Max(mid+1,r,id<<1|1,tl,tr,x);
    pull(id);
}
void update_Min(int l,int r,int id,int tl,int tr,int x){
    if(x>=Max[id] || tr<l || r<tl) return;
    if(tl<=l && r<=tr && x<=Min[id]){
        getnew(id,x);
        return;
    }
    pushdown(id);
    int mid=(l+r)>>1;
    update_Min(l,mid,id<<1,tl,tr,x);update_Min(mid+1,r,id<<1|1,tl,tr,x);
    pull(id);
}
void build(int l,int r,int id){
    if(l==r){
        res[l]=Min[id];
        return;
    }
    pushdown(id);
    int mid=(l+r)>>1;
    build(l,mid,id<<1);build(mid+1,r,id<<1|1);
}

void buildWall(int n, int k, int op[], int left[], int right[],
               int height[], int finalHeight[]){
    for(int i=0;i<k;i++){
        if(op[i]==1) update_Max(0,n-1,1,left[i],right[i],height[i]);
        else update_Min(0,n-1,1,left[i],right[i],height[i]);
    }
    build(0,n-1,1);
    for(int i=0;i<n;i++) finalHeight[i]=res[i];
}

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