Submission #1275401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275401		uzukishinobu	Wall (IOI14_wall)	C++20	100 / 100	430 ms	66976 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

int f[8000005];
int f1[8000005];
int res[2000005];

void push(int id){
    if (f[id]!=f1[id]){
        return;
    }
    f[id*2]=f1[id*2]=f[id];
    f[id*2+1]=f1[id*2+1]=f[id];
}
void update(int id,int l,int r,int x,int y,int val){
    if (val<=f[id] || x>r || y<l){
        return;
    }
    if (l>=x && y>=r && val>f1[id]){
        f[id]=f1[id]=val;
        return;
    }
    int mid=(l+r)/2;
    push(id);
    update(id*2,l,mid,x,y,val);
    update(id*2+1,mid+1,r,x,y,val);
    f[id]=min(f[id*2],f[id*2+1]);
    f1[id]=max(f1[id*2],f1[id*2+1]);
}
void update1(int id,int l,int r,int x,int y,int val){
    if (val>=f1[id] || x>r || y<l){
        return;
    }
    if (l>=x && y>=r && val<f[id]){
        f[id]=f1[id]=val;
        return;
    }
    int mid=(l+r)/2;
    push(id);
    update1(id*2,l,mid,x,y,val);
    update1(id*2+1,mid+1,r,x,y,val);
    f[id]=min(f[id*2],f[id*2+1]);
    f1[id]=max(f1[id*2],f1[id*2+1]);
}
void bruh(int id,int l,int r){
    if (l==r){
        res[l]=f[id];
//        cerr << res[l] << " ";
        return;
    }
    int mid=(l+r)/2;
    push(id);
    bruh(id*2,l,mid);
    bruh(id*2+1,mid+1,r);
}
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(1,0,n-1,left[i],right[i],height[i]);
         }else{
             update1(1,0,n-1,left[i],right[i],height[i]);
         }
//          cerr << "\n";
    }
    bruh(1,0,n-1);
    for (int i=0;i<n;i++){
         finalHeight[i]=res[i];
    }
    return;
}

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