Submission #969022

#	Time	Username	Problem	Language	Result	Execution time	Memory
969022		elotelo966	Wall (IOI14_wall)	C++17	100 / 100	438 ms	107308 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mid (start+end)/2

pair<int,int> lazy[8000000];
int fin[2000000];


inline int push(int node,int cur){
	cur=max(cur,lazy[node].fi);
	cur=min(cur,lazy[node].se);
	return cur;
}

inline void update(int node,int start,int end,int l,int r,int val,int sem){
	if(start>end || start>r || end<l)return ;
	val=push(node,val);
	if(start>=l && end<=r){
		//cout<<node<<" "<<start<<" "<<end<<" "<<l<<" "<<r<<" "<<val<<" "<<sem<<endl;
		if(sem==1)lazy[node].fi=val;
		else lazy[node].se=val;
		//cout<<lazy[node].fi<<" "<<lazy[node].se<<" "<<endl<<endl;
		return ;
	}
	update(node*2,start,mid,l,r,val,sem),update(node*2+1,mid+1,end,l,r,val,sem);
}

inline void finish(int node,int start,int end,int cur){
	if(start>end)return ;
	cur=push(node,cur);
	if(start==end){
		fin[start]=cur;
		return ;
	}
	finish(node*2,start,mid,cur),finish(node*2+1,mid+1,end,cur);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=0;i<=4*n;i++){
		lazy[i]={-INT_MAX,INT_MAX};
	}
	for(int i=k-1;i>=0;i--){
		if(op[i]==1){
			update(1,0,n-1,left[i],right[i],height[i],1);
		}
		else{
			update(1,0,n-1,left[i],right[i],height[i],-1);
		}
	}
	
	finish(1,0,n-1,0);
	
	for(int i=0;i<n;i++){
		finalHeight[i]=fin[i];
		if(fin[i]==-INT_MAX)finalHeight[i]=0;
	}
	
	return;
}

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