Submission #291933

#	Time	Username	Problem	Language	Result	Execution time	Memory
291933		TMJN	Wall (IOI14_wall)	C++17	100 / 100	816 ms	69628 KiB

wall

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

pair<int,int>tree[1<<22];

pair<int,int>merge(pair<int,int>x,pair<int,int>y){
	pair<int,int>p={min(x.first,y.first),max(x.second,y.second)};
	if(p.first<p.second){
		if(x.second>y.first){
			p.second=p.first;
		}
		else{
			p.first=p.second;
		}
	}
	return p;
}

void update(int k,int l,int r,int p,int q,pair<int,int>val){
	if(q<l||r<p)return;
	else if(p<=l&&r<=q){
		tree[k]=merge(tree[k],val);
	}
	else{
		tree[k+k]=merge(tree[k+k],tree[k]);
		tree[k+k+1]=merge(tree[k+k+1],tree[k]);
		tree[k]={0xE869120,0};
		update(k+k,l,(l+r)/2,p,q,val);
		update(k+k+1,(l+r)/2+1,r,p,q,val);
	}
}

int calc(int x){
	pair<int,int>a={0,0};
	x+=(1<<21);
	while(x){
		a=merge(a,tree[x]);
		x/=2;
	}
	return a.first;
}


void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=0;i<(1<<22);i++){
		tree[i]={0,0};
	}
	for(int i=0;i<K;i++){
		if(op[i]==1){
			update(1,0,(1<<21)-1,left[i],right[i],pair<int,int>{0xE869120,height[i]});
		}
		else{
			update(1,0,(1<<21)-1,left[i],right[i],pair<int,int>{height[i],0});
		}
	}
	for(int i=0;i<N;i++){
		finalHeight[i]=calc(i);
	}
}

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