Submission #968916

#	Time	Username	Problem	Language	Result	Execution time	Memory
968916		elotelo966	Wall (IOI14_wall)	C++17	8 / 100	3094 ms	13960 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 void push(int node,int start,int end){
	if(lazy[node].fi==0 && lazy[node].se==0)return ;
	if(start!=end){
		push(node*2,start,mid),push(node*2+1,mid+1,end);
		lazy[node*2]=lazy[node];
		lazy[node*2+1]=lazy[node];
	}
	else{
		if(lazy[node].fi==1)fin[start]=max(fin[start],lazy[node].se);
		else fin[start]=min(fin[start],lazy[node].se);
	}
	lazy[node]=make_pair(0,0);
}

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 ;
	push(node,start,end);
	if(start>=l && end<=r){
		lazy[node]=make_pair(sem,val);
		push(node,start,end);
		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){
	push(node,start,end);
	if(start==end)return ;
	finish(node*2,start,mid),finish(node*2+1,mid+1,end);
}

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){
			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);
	
	for(int i=0;i<n;i++){
		finalHeight[i]=fin[i];
	}
	
	return;
}

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