Submission #878196

#	Time	Username	Problem	Language	Result	Execution time	Memory
878196		JakobZorz	Wall (IOI14_wall)	C++17	100 / 100	561 ms	72528 KiB

wall

#include"wall.h"
#include<iostream>
using namespace std;

const int TREE_SIZE=1<<21;

#define upper first
#define lower second

pair<int,int>tree[2*TREE_SIZE];
bool lazy[2*TREE_SIZE];
void update(int node){
    if(node>=TREE_SIZE)
        return;
    
    if(lazy[node]){
        tree[2*node].upper=min(tree[2*node].upper,tree[node].upper);
        tree[2*node].upper=max(tree[2*node].upper,tree[node].lower);
        tree[2*node].lower=min(tree[2*node].lower,tree[node].upper);
        tree[2*node].lower=max(tree[2*node].lower,tree[node].lower);
        
        tree[2*node+1].upper=min(tree[2*node+1].upper,tree[node].upper);
        tree[2*node+1].upper=max(tree[2*node+1].upper,tree[node].lower);
        tree[2*node+1].lower=min(tree[2*node+1].lower,tree[node].upper);
        tree[2*node+1].lower=max(tree[2*node+1].lower,tree[node].lower);
        
        lazy[2*node]=true;
        lazy[2*node+1]=true;
        lazy[node]=false;
    }
}

void lh_bound(int node,int l,int r,int rl,int rr,pair<int,int>bound){
    update(node);
    
    if(r<=rl||rr<=l)
        return;
    
    if(l<=rl&&rr<=r){
        tree[node].lower=max(tree[node].lower,bound.lower);
        tree[node].lower=min(tree[node].lower,bound.upper);
        tree[node].upper=max(tree[node].upper,bound.lower);
        tree[node].upper=min(tree[node].upper,bound.upper);
        
        lazy[node]=true;
        return;
    }
    
    int mid=(rl+rr)/2;
    lh_bound(2*node,l,r,rl,mid,bound);
    lh_bound(2*node+1,l,r,mid,rr,bound);
    
    tree[node].lower=min(tree[2*node].lower,tree[2*node+1].lower);
    tree[node].upper=max(tree[2*node].upper,tree[2*node+1].upper);
}

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){
            // adding phase
            pair<int,int>bound;
            bound.lower=height[i];
            bound.upper=1000000000;
            lh_bound(1,left[i],right[i]+1,0,TREE_SIZE,bound);
        }else{
            // removing phase
            pair<int,int>bound;
            bound.lower=-1000000000;
            bound.upper=height[i];
            lh_bound(1,left[i],right[i]+1,0,TREE_SIZE,bound);
        }
    }
    
    for(int i=1;i<2*TREE_SIZE;i++)
        update(i);
    
    for(int i=0;i<n;i++)
        finalHeight[i]=tree[TREE_SIZE+i].lower;
}

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