Submission #1239914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239914		Minbaev	Wall (IOI14_wall)	C++20	100 / 100	426 ms	67008 KiB

wall

#include "wall.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
int ans[2000005];
int v[8000005][2];
    void upd(int x,int mn,int mx){
        v[x][0]=min(max(mn,v[x][0]),mx);
        v[x][1]=min(max(mn,v[x][1]),mx);
    }
    void push(int x,int l,int r){
        if(l!=r){
            upd(x*2,v[x][0],v[x][1]);
            upd(x*2+1,v[x][0],v[x][1]);
        }
        v[x][1]=INT_MAX;
        v[x][0]=0;
    }
    void update(int x,int lx,int rx,int l,int r,int mn,int mx){
        if(lx>=l&&r>=rx){
            upd(x,mn,mx);
            return;
        }
        if(rx<l||lx>r)
            return;
        push(x,lx,rx);
        int m=(lx+rx)/2;
        update(x*2,lx,m,l,r,mn,mx);
        update(x*2+1,m+1,rx,l,r,mn,mx);
    }
    void build(int  x,int l,int r){
        if(l==r){
            ans[l]=v[x][0];
            return;
        }
        push(x,l,r);
        int m=(l+r)/2;
        build(x*2,l,m);
        build(x*2+1,m+1,r);
    }




void buildWall(int n, int k, int w[], int l[], int r[], int h[], int a[]){

    for(int i=0;i<k;i++){
        int mn=(w[i]==1 ? h[i]:0),mx=(w[i]==2 ? h[i]:INT_MAX);
        update(1,0,n-1,l[i],r[i],mn,mx);
    }
    build(1,0,n-1);
    for(int i=0;i<n;i++)
        a[i]=ans[i];
    return ;
}
/*


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: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39