Submission #138835

#	Time	Username	Problem	Language	Result	Execution time	Memory
138835		Runtime_error_	Wall (IOI14_wall)	C++14	100 / 100	1547 ms	69636 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define le node+node
#define ri node+node+1
#define mid (l+r)/2
#define ll long long
using namespace std;
const int inf = 2e6+9,MX = 1e9+9;
int opmin[inf<<2],opmax[inf<<2];

void build(int node,int l,int r){

    opmin[node] = MX;
    opmax[node] = 0;
    if(l == r)
        return;
    build(le,l,mid);
    build(ri,mid+1,r);
}

void tochild(int child,int node){
    opmin[child] = min( opmin[child] , opmin[node] );//If you lower to height h on the child and to
    //height h' on the parent after that, only min(h,h') will take effect

    opmax[child] = max( opmax[child] , opmax[node] );//If you increase to height h on the child and then increase to
    //height h' on the parent, only max(h,h') will take effect

    opmin[child] = max( opmin[child] , opmax[node] );//If you decrease to height h on the child and then increase to
     //height h' on the parent, with h'>h, then the first operation will lose effect
    opmax[child] = min( opmax[child] , opmin[node] );//If you increase to height h on the child and then decrease to
    // height h' on the parent, with h'<h, then the first operation will lose effect.

}

void push(int node,int l,int r){

    if(l == r)
        return ;

    tochild(le,node);
    tochild(ri,node);
    opmax[node] = 0;
    opmin[node] = MX;
}

void update(int node,int l,int r,int x,int y,int val,int type){//type 2 minimize 1 maximize

    push(node,l,r);
    if(l>r || r<x || l>y)
        return ;
    if(l>=x && r<=y){
        if(type == 2)
            opmin[node] = min(opmin[node],val),opmax[node] = min(opmax[node],val);
        else
            opmax[node] = max(opmax[node],val) , opmin[node] = max(opmin[node],val);
        push(node,l,r);
        return ;
    }
    update(le,l,mid,x,y,val,type);
    update(ri,mid+1,r,x,y,val,type);
}

int query(int node,int l,int r,int idx){
    push(node,l,r);
    if(l == r)
        return min(opmin[node],opmax[node]);
    if(idx <= mid)
        return query(le,l,mid,idx);
    return query(ri,mid+1,r,idx);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){

    build(1,1,n);
    for(int i=0;i<k;i++)
        update(1,1,n,left[i]+1,right[i]+1,height[i],op[i]);
    for(int i=1;i<=n;i++)
        finalHeight[i-1] = query(1,1,n,i);
}

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