제출 #373728

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
373728		Temmie	벽 (IOI14_wall)	C++17	100 / 100	1261 ms	82924 KiB

wall

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

struct Item {
	
	int max;
	int min;
	
	Item() : max(1 << 30), min(-1) { }
	
	void merge_max(int value) {
		max = std::min(max, value);
		min = std::min(min, max);
	}
	
	void merge_min(int value) {
		min = std::max(min, value);
		max = std::max(max, min);
	}
	
	void merge(const Item& oth) {
		max = std::min(max, oth.max);
		min = std::min(min, max);
		min = std::max(min, oth.min);
		max = std::max(max, min);
	}
	
	void merge(const Item& oth_a, const Item& oth_b) {
		max = std::min(oth_a.max, oth_b.max);
		min = std::max(oth_a.min, oth_b.min);
		max = std::max(max, min);
		min = std::min(min, max);
	}
	
};

struct Seg {
	
	int size;
	
	std::vector <Item> v, lazy;
	
	Seg(int _size) {
		size = 1;
		while (size < _size) size <<= 1;
		v.resize(size << 1, Item());
		lazy.resize(size << 1, Item());
	}
	
	void update(bool type, int value, int target_left, int target_right, int now, int left, int right) {
		if (lazy[now].max != 1 << 30 || lazy[now].min != -1) {
			v[now].merge(lazy[now]);
			if (right - left - 1) {
				lazy[now * 2 + 1].merge(lazy[now]);
				lazy[now * 2 + 2].merge(lazy[now]);
			}
			lazy[now] = Item();
		}
		if (left >= target_right || right <= target_left)
			return;
		if (left >= target_left && right <= target_right) {
			if (type)
				v[now].merge_max(value);
			else
				v[now].merge_min(value);
			if (right - left - 1) {
				if (type)
					lazy[now * 2 + 1].merge_max(value),
					lazy[now * 2 + 2].merge_max(value);
				else
					lazy[now * 2 + 1].merge_min(value),
					lazy[now * 2 + 2].merge_min(value);
			}
			return;
		}
		int mid = (left + right) >> 1;
		update(type, value, target_left, target_right, now * 2 + 1, left, mid);
		update(type, value, target_left, target_right, now * 2 + 2, mid, right);
		v[now].merge(v[now * 2 + 1], v[now * 2 + 2]);
	}
	
	void update(bool type, int value, int left, int right) {
		update(type, value, left, right, 0, 0, size);
	}
	
	int get(int index, int now, int left, int right) {
		if (lazy[now].max != 1 << 30 || lazy[now].min != -1) {
			v[now].merge(lazy[now]);
			if (right - left - 1) {
				lazy[now * 2 + 1].merge(lazy[now]);
				lazy[now * 2 + 2].merge(lazy[now]);
			}
			lazy[now] = Item();
		}
		if (!(right - left - 1))
			return std::max(0, v[now].min);
		int mid = (left + right) >> 1;
		if (index < mid)
			return get(index, now * 2 + 1, left, mid);
		return get(index, now * 2 + 2, mid, right);
	}
	
	int get(int index) {
		return get(index, 0, 0, size);
	}
	
	void print() {
		int cnt = 2;
		for (int i = 0; i < (int)v.size(); i++) {
			if (i == cnt - 1) {
				cnt <<= 1;
				std::cout << "\n";
			}
			std::cout << v[i].min << " ";
		}
		std::cout << "\n";
	}
	
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	Seg seg(n);
	for (int i = 0; i < k; i++)
		seg.update(op[i] == 2, height[i], left[i], right[i] + 1);
	for (int i = 0; i < n; i++) finalHeight[i] = seg.get(i);
}

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