Submission #373682

#	Time	Username	Problem	Language	Result	Execution time	Memory
373682		sofapuden	Wall (IOI14_wall)	C++14	24 / 100	642 ms	22644 KiB

wall

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

using namespace std;

const int maxn = 2e6+5;
const int maxv = 1<<30;

vector<array<int,2>> seg;

void add(int l, int r, int lb, int rb, int p, int q, array<int,2> pre){
	seg[p] = {min(max(pre[0],seg[p][0]),pre[1]),max(pre[0],min(pre[1],seg[p][1]))};
	if(l > rb || r < lb){
		return;
	}
	if(l >= lb && r <= rb){
		seg[p] = {max(q,seg[p][0]), max(q,seg[p][1])};
		return;
	}
	int mid = (l+r)>>1;
	add(l,mid,lb,rb,p<<1,q,seg[p]);
	add(mid+1,r,lb,rb,(p<<1)+1,q,seg[p]);
	seg[p][1] = max(seg[p][1],q);
}

void rem(int l, int r, int lb, int rb, int p, int q, array<int,2> pre){
	seg[p] = {min(max(pre[0],seg[p][0]),pre[1]),max(pre[0],min(pre[1],seg[p][1]))};
	if(l > rb || r < lb){
		return;
	}
	if(l >= lb && r <= rb){
		seg[p] = {min(q,seg[p][0]), min(q,seg[p][1])};
		return;
	}
	int mid = (l+r)>>1;
	rem(l,mid,lb,rb,p<<1,q,seg[p]);
	rem(mid+1,r,lb,rb,(p<<1)+1,q,seg[p]);
	seg[p][0] = min(q, seg[p][0]);
}

void update(int l, int r, int p, array<int,2> pre, vector<int> &v, int val, int mx){
	if(l == r){
		v[l] = min(mx,max(seg[p][0],val));
		return;
	}
	int mid = (l+r)>>1;
	update(l,mid,p<<1,seg[p],v,max(val,seg[p][0]),min(mx,seg[p][1]));
	update(mid+1,r,(p<<1)+1,seg[p],v,max(val,seg[p][0]),min(mx,seg[p][1]));
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	seg.resize(4*n,{0,maxv});
	vector<int> v(n,0);
	for(int i = 0; i < k; ++i){
		if(op[i] == 1){
			add(0,n-1,left[i],right[i],1,height[i],{0,maxv});
		}
		else{
			rem(0,n-1,left[i],right[i],1,height[i],{0,maxv});
		}
	}
	update(0,n-1,1,{0,maxv},v,0,maxv);
	for(int i = 0; i < n; ++i){
		finalHeight[i] = v[i];
	}
	return;
}

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