제출 #373705

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

wall

#include "wall.h"

#include <bits/stdc++.h>

const int MX = 100000;

struct Node {
	
	Node *l, *r;
	int min, max;
	
	Node() : l(nullptr), r(nullptr), min(0), max(MX) { }
	~Node() {
		if (l)
			delete(l);
		if (r)
			delete(r);
	}
	
	void update() {
		if (!l) l = new Node;
		if (!r) r = new Node;
		min = std::max(l->min, r->min);
		max = std::min(l->max, r->max);
		if (min > max) {
			if (l->min > r->max)
				min = max = r->max;
			if (l->max < r->min)
				min = max = r->min;
		}
	}
	
};

Node* head = new Node;

void add(int index, int min, int max, int left, int right, Node*& node) {
	if (!node)
		node = new Node;
	if (left == right) {
		node->min = min;
		node->max = max;
		return;
	}
	int mid = (left + right) >> 1;
	if (mid >= index) add(index, min, max, left, mid, node->l);
	else add(index, min, max, mid + 1, right, node->r);
	node->update();
}

struct Operation {
	int index;
	int min, max;
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	std::vector <std::vector <Operation>> operations(n + 1);
	for (int i = 0; i < k; i++) {
		operations[left[i]].push_back({ i, op[i] ? height[i] : 0, op[i] ? MX : height[i] });
		operations[right[i] + 1].push_back({ i, 0, MX });
	}
	for (int i = 0; i < n; i++) {
		for (const auto& o : operations[i])
			add(o.index, o.min, o.max, 0, k - 1, head);
		finalHeight[i] = head->min;
	}
	delete(head);
}

//int main() {
	
	//int n = 10;
	//int k = 6;
	//int op[6] = { 1, 0, 0, 1, 1, 0 };
	//int left[6] = { 1, 4, 3, 0, 2, 6 };
	//int right[6] = { 8, 9, 6, 5, 2, 7 };
	//int height[6] = { 4, 1, 5, 3, 5, 0 };
	//int finalHeight[10];
	//buildWall(n, k, op, left, right, height, finalHeight);
	//for (int i = 0; i < n; i++)
		//std::cout << finalHeight[i] << " \n"[i == n - 1];
	
//}

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