Submission #378047

#	Time	Username	Problem	Language	Result	Execution time	Memory
378047		applemethod	Wall (IOI14_wall)	C++14	0 / 100	201 ms	13980 KiB

wall

#include <iostream>
#include <algorithm>

#include "wall.h"

using namespace std;

using ll = long long;

const int maxn = 2000010;

struct segtree_node {
	segtree_node* left_child, * right_child;
	int left_bound, right_bound;
	ll lazy_min, lazy_max;

	void update(ll val) {
		if (val < 0) {
			lazy_max = max(lazy_max, -val);
			lazy_min = max(lazy_min, lazy_max);
		} else {
			lazy_min = min(lazy_min, val);
			lazy_max = min(lazy_max, lazy_max);
		}
	}
	void merge() {

	}
	void prop() {
		if (left_child != NULL) {
			left_child->update(lazy_min);
			left_child->update(-lazy_max);
		}
		if (right_child != NULL) {
			right_child->update(lazy_min);
			right_child->update(-lazy_max);
		}
	}

	void update(int left, int right, ll val) {
		prop();
		if (left_bound >= left && right_bound <= right) {
			update(val);
			return;
		}
		int mid = left_bound + (right_bound - left_bound) / 2;
		if (left <= mid) {
			if (left_child == NULL) {
				left_child = new segtree_node(left_bound, mid);
			}
			left_child->update(left, right, val);
		}
		if (right > mid) {
			if (right_child == NULL) {
				right_child = new segtree_node(mid + 1, right_bound);
			}
			right_child->update(left, right, val);
		}
		merge();
	}
	ll query(int left, int right) {
		prop();
		if (left_bound >= left && right_bound <= right) {
			return min(lazy_min, lazy_max);
		}
		int mid = left_bound + (right_bound - left_bound) / 2;
		ll res = 0;
		if (left <= mid) {
			if (left_child == NULL) {
				left_child = new segtree_node(left_bound, mid);
			}
			res += left_child->query(left, right);
		}
		if (right > mid) {
			if (right_child == NULL) {
				right_child = new segtree_node(mid + 1, right_bound);
			}
			res += right_child->query(left, right);
		}
		return res;
	}

	segtree_node() {
		left_child = right_child = NULL;
		left_bound = right_bound = -1;
		lazy_min = lazy_max = 0;
	}
	segtree_node(int left, int right) {
		left_child = right_child = NULL;
		left_bound = left; right_bound = right;
		lazy_min = lazy_max = 0;
	}
};

segtree_node* segtree;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	segtree = new segtree_node(0, n - 1);
	for (int i = 0; i < k; i++) {
		// cout << (op[i] * 2 - 3) * height[i] << endl;
		segtree->update(left[i], right[i], (op[i] * 2 - 3) * height[i]);
	}
	for (int i = 0; i < n; i++) {
		finalHeight[i] = segtree->query(i, i);
	}
}

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