Submission #585551

#	Time	Username	Problem	Language	Result	Execution time	Memory
585551		SeDunion	Wall (IOI14_wall)	C++17	100 / 100	866 ms	69740 KiB

wall

#include "wall.h"
#include<iostream>

using namespace std;

const int N = 2e6 + 123;
const int inf = 1e9 + 123;

int n;

int fl[N << 2], fr[N << 2];

void build(int l = 0, int r = n, int v = 1) {
	fl[v] = 0, fr[v] = inf;
	if (r - l == 1) return;
	int m = (l + r) >> 1;
	build(l, m, v << 1);
	build(m, r, v<<1|1);
}

void make(int &al, int &ar, int bl, int br) {
	if (ar < bl) {
		al = bl, ar = bl;
	} else if (br < al) {
		al = br, ar = br;
	} else {
		al = max(al, bl);
		ar = min(ar, br);
	}
}

void push(int v, int l, int r) {
	if (r - l > 1) {
		make(fl[v << 1], fr[v << 1], fl[v], fr[v]);
		make(fl[v<<1|1], fr[v<<1|1], fl[v], fr[v]);
		fl[v] = 0, fr[v] = inf;
	}
}

void upd(int L, int R, int cl, int cr, int l = 0, int r = n, int v = 1) {
	push(v, l, r);
	if (L <= l && r <= R) {
		make(fl[v], fr[v], cl, cr);
		push(v, l, r);
		return;
	}
	if (L >= r || l >= R) return;
	int m = (l + r) >> 1;
	upd(L, R, cl, cr, l, m, v << 1);
	upd(L, R, cl, cr, m, r, v<<1|1);
}

int a[N];

void show(int l = 0, int r = n, int v = 1) {
	push(v, l, r);
	if (r - l == 1) {
		a[l] = fl[v];
		//cout << "[" << fl[v] << ", " << fr[v] << "] ";
		return;
	}
	int m = (l + r) >> 1;
	show(l, m, v << 1);
	show(m, r, v<<1|1);
}

void buildWall(int n_, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	n = n_;
	build();
	for (int i = 0 ; i < k ; ++ i) {
		if (op[i] == 1) {
			upd(left[i], right[i] + 1, height[i], inf);
		} else {
			upd(left[i], right[i] + 1, 0, height[i]);
		}
	}
	show();
	for (int i = 0 ; i < n ; ++ i) {
		finalHeight[i] = a[i];
	}
}

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