제출 #1192345

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192345		TroySer	벽 (IOI14_wall)	C++20	100 / 100	732 ms	214324 KiB

wall

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

using namespace std;
using ll = int;

const ll INF = 1e9;

class SegTreeNode {

	private:

		ll l, r;
		SegTreeNode *leftChild, *rightChild;
		ll lowerBound, upperBound;

	public:

		SegTreeNode(ll l, ll r) {

			this->l = l, this->r = r;
			ll lowerBound = 0, upperBound = INF;
			
			if (l == r) {
				leftChild = nullptr;
				rightChild = nullptr;
				return;
			}

			ll M = (l + r) / 2;
			leftChild = new SegTreeNode(l, M);
			rightChild = new SegTreeNode(M + 1, r);

		}

		void fixBounds(ll lb, ll ub) { // this took me quite a while to get :') even looking at reflections, editorials, submissions, etc.

			// basically setting the "strictest" possible bounds for the wall
			
			upperBound = min(upperBound, ub); // if ub >= upperBound, i.e. if the "highest block" is higher than what we already have as "highest block", then idgaf
			lowerBound = min(lowerBound, upperBound); // lower bound must be at most upper bound

			lowerBound = max(lowerBound, lb); // if lb <= lowerBound, i.e. if the "lowest block" is lower than what we already have as "lowest", then idgaf
			upperBound = max(lowerBound, upperBound); // upper bound must be at least lower bound

		}

		void propagate() {
			if (leftChild != nullptr) {
				leftChild->fixBounds(lowerBound, upperBound);
				rightChild->fixBounds(lowerBound, upperBound);
				lowerBound = 0, upperBound = INF;
			}
		}

		ll query(ll i) {

			if (l == r) {
				return lowerBound;
			}

			ll M = (l + r) / 2;
			propagate();
			if (i <= M) return leftChild->query(i);
			else return rightChild->query(i);

		}

		void addWall(ll ql, ll qr, ll newHeight) {

			if (l > qr || r < ql) return;

			if (ql <= l && r <= qr) {
				fixBounds(newHeight, INF); // only from newHeight to INF now
				propagate();
				return;
			}

			ll M = (l + r) / 2;
			propagate();
			leftChild->addWall(ql, qr, newHeight);
			rightChild->addWall(ql, qr, newHeight);

		}

		void removeWall(ll ql, ll qr, ll newHeight) {

			if (l > qr || r < ql) return;

			if (ql <= l && r <= qr) {
				fixBounds(0, newHeight); // only from 0 to newHeight now
				propagate();
				return;
			}

			ll M = (l + r) / 2;
			propagate();
			leftChild->removeWall(ql, qr, newHeight);
			rightChild->removeWall(ql, qr, newHeight);

		}

};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  	
	SegTreeNode* st = new SegTreeNode(0, n - 1);
	
	for (ll i = 0; i < k; i++) {

		if (op[i] == 1) {
			st->addWall(left[i], right[i], height[i]);
		} else {
			st->removeWall(left[i], right[i], height[i]);
		}

	}

	for (ll i = 0; i < n; i++) {
		finalHeight[i] = st->query(i);
	}

}

// int main() {

// 	int n = 10, k = 6;

// 	int op[6] = {1, 2, 2, 1, 1, 2};
// 	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);

// 	cout << "finalHeight: ";
// 	for (auto l: finalHeight) {
// 		cout << l << ", ";
// 	}
// 	cout << endl;

// }

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