Submission #779239

#	Time	Username	Problem	Language	Result	Execution time	Memory
779239		Sohsoh84	Wall (IOI14_wall)	C++17	100 / 100	613 ms	101072 KiB

wall

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

using namespace std;

typedef pair<int, int> pll;

#define X		first
#define Y		second

const int MAXN = 1e7 + 10;

pll sg[MAXN];
int n, lz[MAXN], A[MAXN];

inline pll merge(pll a, pll b) {
	a.X = min(a.X, b.X);
	a.Y = max(a.Y, b.Y);
	return a;
}

void build(int l = 0, int r = n - 1, int v = 1) {
	lz[v] = -1;
	if (l == r) sg[v] = {0, 0};
	else {
		int mid = (l + r) >> 1;
		build(l, mid, v << 1);
		build(mid + 1, r, v << 1 | 1);
		sg[v] = merge(sg[v << 1], sg[v << 1 | 1]);
	}
}

inline void push(int v) {
	if (lz[v] >= 0) {
		sg[v] = {lz[v], lz[v]};
		if ((v << 1 | 1) < MAXN) lz[v << 1] = lz[v << 1 | 1] = lz[v];
	}

	lz[v] = -1;
}

void q_max(int ql, int qr, int val, int l = 0, int r = n - 1, int v = 1) {
	push(v);
	if (ql > r || qr < l || sg[v].X >= val) return;
	if (ql <= l && qr >= r) {
		if (sg[v].Y <= val) {
			lz[v] = val;
			push(v);
			return;
		}	
	}

	int mid = (l + r) >> 1;
	q_max(ql, qr, val, l, mid, v << 1);
	q_max(ql, qr, val, mid + 1, r, v << 1 | 1);
	sg[v] = merge(sg[v << 1], sg[v << 1 | 1]);
	return;
}

void q_min(int ql, int qr, int val, int l = 0, int r = n - 1, int v = 1) {
	push(v);
	if (ql > r || qr < l || sg[v].Y <= val) return;
	if (ql <= l && qr >= r) {
		if (sg[v].X >= val) {
			lz[v] = val;
			push(v);
			return;
		}	
	}

	int mid = (l + r) >> 1;
	q_min(ql, qr, val, l, mid, v << 1);
	q_min(ql, qr, val, mid + 1, r, v << 1 | 1);
	sg[v] = merge(sg[v << 1], sg[v << 1 | 1]);
	return;
}

void print(int l = 0, int r = n - 1, int v = 1) {
	push(v);
	if (l == r) {
		A[l] = sg[v].X;
		return;
	}

	int mid = (l + r) >> 1;
	print(l, mid, v << 1);
	print(mid + 1, 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) q_max(left[i], right[i], height[i]);
		else q_min(left[i], right[i], height[i]);
	}

	print();
	for (int i = 0; i < n; i++) finalHeight[i] = A[i];
	return;
}

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