Submission #39307

#	Time	Username	Problem	Language	Result	Execution time	Memory
39307		mohammad_kilani	Wall (IOI14_wall)	C++14	100 / 100	803 ms	80156 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define oo 2000000000
const int N = 2000010;
pair<int,int> seg[4 * N];

void update(int s,int e,int idx,int l,int r,int val,bool b){
	val = max(val,seg[idx].first);
	val = min(val,seg[idx].second);
	if(s > r || e < l) return;
	if(s >= l && e <= r){
		if(!b) seg[idx].first = val; else seg[idx].second = val;
		return;
	}
	update(s,(s+e)/2,idx*2,l,r,val,b);
	update((s+e)/2+1,e,idx*2+1,l,r,val,b);
}

void make(int s,int e,int idx,int cur,int *arr){
	cur = max(cur,seg[idx].first);
	cur = min(cur,seg[idx].second);
	if(s == e){
		arr[s] = cur;
		return;
	}
	make(s,(s+e)/2,idx*2,cur,arr);
	make((s+e)/2+1,e,idx*2+1,cur,arr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=1;i<=4 * n;i++) seg[i] = make_pair(0,oo);
	for(int i=k-1;i>=0;i--)
		update(0,n-1,1,left[i],right[i],height[i],op[i]-1);
	make(0,n-1,1,0,finalHeight);
  	return;
}

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