제출 #377345

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
377345		applemethod	벽 (IOI14_wall)	C++14	0 / 100	212 ms	14172 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;

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

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

	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 lazy;
		}
		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 = 0;
	}
	segtree_node(int left, int right) {
		left_child = right_child = NULL;
		left_bound = left; right_bound = right;
		lazy = 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