Submission #373713

#	Time	Username	Problem	Language	Result	Execution time	Memory
373713		Temmie	Wall (IOI14_wall)	C++17	0 / 100	344 ms	52788 KiB

wall

#include "wall.h"

#include <bits/stdc++.h>

const int MX = 100000;

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

Node* head = new Node;

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

struct Operation {
	int index;
	int mn, mx;
};

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.mn, o.mx, 0, k - 1, head);
		finalHeight[i] = head->mn;
	}
	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