제출 #1150508

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150508		pinbu	벽 (IOI14_wall)	C++20	100 / 100	590 ms	59180 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
#define fi first
#define se second
using namespace std;

const int MXn = 2e6 + 5, oo = 1e5;

int N;
struct type {
	int LL, RR;
} node[(1 << 22) + 5];
void build(int id = 1, int l = 0, int r = N) {
	if (l == r) {
		node[id] = {0, 0};
		return;
	}
	node[id] = {0, oo};
	int mid = (l + r) >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
}
void modify(int id, int t, int val) {
	// if (val == 3 && id == 24) cerr << t << ' ' << node[id].LL << ' ' << node[id].RR << '\n';
	if (t == 1) {
		// if (node[id].RR < val) node[id].b = true;
		node[id].LL = max(node[id].LL, val);
		node[id].RR = max(node[id].RR, val);
	} else {
		// if (node[id].LL > val) node[id].b = false;
		node[id].LL = min(node[id].LL, val);
		node[id].RR = min(node[id].RR, val);
	}
	// if (val == 3 && id == 24) cerr << t << ' ' << node[id].LL << ' ' << node[id].RR << '\n';
}
void push(int id) {
	// if (node[id].b) {
		modify(id << 1, 1, node[id].LL);
		modify(id << 1, 2, node[id].RR);
		modify(id << 1 | 1, 1, node[id].LL);
		modify(id << 1 | 1, 2, node[id].RR);
	// } else {
		// modify(id << 1, 2, node[id].LL);
		// modify(id << 1, 1, node[id].RR);
		// modify(id << 1 | 1, 2, node[id].LL);
		// modify(id << 1 | 1, 1, node[id].RR);
	// }
	node[id] = {0, oo};
}
void update(int t, int Lf, int Rt, int val, int id = 1, int l = 0, int r = N) {
	if (Lf <= l && r <= Rt) {
		modify(id, t, val);
		return;
	}
	push(id);
	int mid = (l + r) >> 1;
	if (Lf <= mid) update(t, Lf, Rt, val, id << 1, l, mid);
	if (Rt > mid) update(t, Lf, Rt, val, id << 1 | 1, mid + 1, r);
}
int findh(int i) {
	int id = 1, l = 0, r = N;
	while (l < r) {
		push(id);
		int mid = (l + r) >> 1;
		if (i <= mid) {
			id <<= 1;
			r = mid;
		} else {
			id = id << 1 | 1;
			l = mid + 1;
		}
	}
	return node[id].LL;
}

void buildWall(int w, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	N = w - 1;
	build();
	for (int i = 0; i < k; i++) update(op[i], left[i], right[i], height[i]);
	for (int i = 0; i < w; i++) finalHeight[i] = findh(i);
}

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