Submission #282468

#	Time	Username	Problem	Language	Result	Execution time	Memory
282468		Saboon	Wall (IOI14_wall)	C++14	100 / 100	991 ms	100984 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10;

int segmx[4*maxn], segmn[4*maxn], seglz[4*maxn];

void shift(int id){
	if (seglz[id] == -1)
		return;
	segmn[2*id+0] = segmx[2*id+0] = seglz[2*id+0] = seglz[id];
	segmn[2*id+1] = segmx[2*id+1] = seglz[2*id+1] = seglz[id];
	seglz[id] = -1;
}

int get(int id, int L, int R, int idx){
	if (L + 1 == R)
		return segmn[id];
	shift(id);
	int mid = (L + R) >> 1;
	if (idx < mid)
		return get(2*id+0, L, mid, idx);
	return get(2*id+1, mid, R, idx);
}

void add(int id, int L, int R, int l, int r, int x){
	if (r <= L or R <= l or segmn[id] >= x)
		return;
	if (l <= L and R <= r and segmx[id] <= x){
		segmn[id] = segmx[id] = seglz[id] = x;
		return;
	}
	shift(id);
	int mid = (L + R) >> 1;
	add(2*id+0, L, mid, l, r, x);
	add(2*id+1, mid, R, l, r, x);
	segmx[id] = max(segmx[2*id+0], segmx[2*id+1]);
	segmn[id] = min(segmn[2*id+0], segmn[2*id+1]);
}

void del(int id, int L, int R, int l, int r, int x){
	if (r <= L or R <= l or segmx[id] <= x)
		return;
	if (l <= L and R <= r and segmn[id] >= x){
		segmn[id] = segmx[id] = seglz[id] = x;
		return;
	}
	shift(id);
	int mid = (L + R) >> 1;
	del(2*id+0, L, mid, l, r, x);
	del(2*id+1, mid, R, l, r, x);
	segmx[id] = max(segmx[2*id+0], segmx[2*id+1]);
	segmn[id] = min(segmn[2*id+0], segmn[2*id+1]);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	memset(seglz, -1, sizeof seglz);
	for (int i = 0; i < k; i++){
		if (op[i] == 1)
			add(1, 0, n, left[i], right[i]+1, height[i]);
		else
			del(1, 0, n, left[i], right[i]+1, height[i]);
	}
	for (int i = 0; i < n; i++)
		finalHeight[i] = get(1, 0, n, i);
	return;
}

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