Submission #503717

#	Time	Username	Problem	Language	Result	Execution time	Memory
503717		atoiz	Weirdtree (RMI21_weirdtree)	C++14	100 / 100	622 ms	31864 KiB

weirdtree

#include "weirdtree.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <cassert>

using namespace std;

struct SegmentTree {
	static const int INF = 1e9;
	struct Node {
		int fir, sec, cnt, laz;
		int64_t tot;
		Node(int _fir = 0, int _sec = 0, int _cnt = 0, int _laz = INF, int64_t _tot = 0):
			fir(_fir), sec(_sec), cnt(_cnt), laz(_laz), tot(_tot) {}

		void apply(int x) {
			if (x < fir) tot -= (int64_t) (fir - x) * cnt, fir = laz = x;
		}

		void push(Node &lhs, Node &rhs) {
			lhs.apply(laz), rhs.apply(laz), laz = INF;
		}

		void pull(Node &lhs, Node &rhs) {
			tot = lhs.tot + rhs.tot;
			if (lhs.fir < rhs.fir) {
				fir = rhs.fir;
				sec = max(lhs.fir, rhs.sec);
				cnt = rhs.cnt;
			} else if (lhs.fir > rhs.fir) {
				fir = lhs.fir;
				sec = max(lhs.sec, rhs.fir);
				cnt = lhs.cnt;
			} else {
				fir = lhs.fir;
				sec = max(lhs.sec, rhs.sec);
				cnt = lhs.cnt + rhs.cnt;
			}
		}
	};

	int n;
	vector<Node> a;

	void build(int rt, int lo, int hi, vector<int> &vec) {
		if (lo == hi) a[rt] = {vec[lo], -1, 1, INF, vec[lo]};
		else {
			int md = (lo + hi) >> 1, lc = rt << 1, rc = lc ^ 1;
			build(lc, lo, md, vec), build(rc, md + 1, hi, vec);
			a[rt].pull(a[lc], a[rc]);
		}
	}

	SegmentTree(vector<int> vec = {0, 1}) {
		n = (int) vec.size() - 1;
		a.resize(n * 4 + 10);
		build(1, 1, n, vec);
	}

	void minimize(int rt, int lo, int hi, int x) {
		if (a[rt].fir <= x) return;
		if (a[rt].sec < x) return a[rt].apply(x);
		int md = (lo + hi) >> 1, lc = rt << 1, rc = lc ^ 1;
		a[rt].push(a[lc], a[rc]);
		minimize(lc, lo, md, x), minimize(rc, md + 1, hi, x);
		a[rt].pull(a[lc], a[rc]);
	}

	void traverse(int rt, int lo, int hi, int l, int r, vector<tuple<int, int, int>> &vec) {
		if (l <= lo && hi <= r) return vec.emplace_back(rt, lo, hi), void();
		if (hi < l || r < lo) return;
		int md = (lo + hi) >> 1, lc = rt << 1, rc = lc ^ 1;
		a[rt].push(a[lc], a[rc]);
		traverse(lc, lo, md, l, r, vec), traverse(rc, md + 1, hi, l, r, vec);
		a[rt].pull(a[lc], a[rc]);
	}

	void cut(int l, int r, int x) {
		vector<tuple<int, int, int>> vec;
		traverse(1, 1, n, l, r, vec);

		while (x) {
			int fir = 0, sec = 0;
			const auto upd = [&fir, &sec](int val) {
				if (fir == val || sec == val) return;
				if (fir < val) swap(fir, val);
				if (sec < val) swap(sec, val);
			};
			for (auto [rt, lo, hi] : vec) {
				upd(a[rt].fir), upd(a[rt].sec);
			}
			if (fir == 0) break;

			int cnt = 0;
			for (auto [rt, lo, hi] : vec) if (fir == a[rt].fir) {
				cnt += a[rt].cnt;
			}
			assert(cnt > 0);

			if (cnt > x) {
				for (auto [rt, lo, hi] : vec) if (fir == a[rt].fir) {
					if (a[rt].cnt <= x) {
						x -= a[rt].cnt;
						minimize(rt, lo, hi, fir - 1);
					} else {
						int start_rt = rt;
						while (x) {
							int md = (lo + hi) >> 1, lc = rt << 1, rc = lc ^ 1;
							a[rt].push(a[lc], a[rc]);
							if (a[lc].fir == fir && a[lc].cnt > x) {
								rt = lc, hi = md;
							} else {
								x -= (a[lc].fir == fir) * a[lc].cnt;
								minimize(lc, lo, md, fir - 1);
								rt = rc, lo = md + 1;
							}
						}

						for (rt >>= 1; rt >= start_rt; rt >>= 1) a[rt].pull(a[rt << 1], a[rt << 1 | 1]);
						break;
					}
				}
				break;
			}

			if ((int64_t) (fir - sec) * cnt > x) sec = fir - x / cnt;
			x -= (fir - sec) * cnt;
			for (auto [rt, lo, hi] : vec) if (fir == a[rt].fir) {
				minimize(rt, lo, hi, sec);
			}
		}

		vec.clear();
		traverse(1, 1, n, l, r, vec);
	}

	void magic(int i, int x) {
		int rt = 1, lo = 1, hi = n;
		while (lo < hi) {
			int md = (lo + hi) >> 1, lc = rt << 1, rc = lc ^ 1;
			a[rt].push(a[lc], a[rc]);
			if (i <= md) rt = lc, hi = md;
			else rt = rc, lo = md + 1;
		}
		a[rt] = {x, -1, 1, INF, x};
		for (rt >>= 1; rt > 0; rt >>= 1) a[rt].pull(a[rt << 1], a[rt << 1 | 1]);
	}

	int64_t inspect(int l, int r) {
		vector<tuple<int, int, int>> vec;
		traverse(1, 1, n, l, r, vec);
		int64_t res = 0;
		for (auto [rt, lo, hi] : vec) res += a[rt].tot;
		return res;
	}
} st;

void initialise(int N, int Q, int h[]) {
	st = SegmentTree(vector<int>(h, h + N + 1));
}
void cut(int l, int r, int k) {
	return st.cut(l, r, k);
}
void magic(int i, int x) {
	return st.magic(i, x);
}
long long int inspect(int l, int r) {
	return st.inspect(l, r);
}

Compilation message (stderr)

weirdtree.cpp: In member function 'void SegmentTree::cut(int, int, int)':
weirdtree.cpp:91:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |    for (auto [rt, lo, hi] : vec) {
      |              ^
weirdtree.cpp:97:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |    for (auto [rt, lo, hi] : vec) if (fir == a[rt].fir) {
      |              ^
weirdtree.cpp:103:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |     for (auto [rt, lo, hi] : vec) if (fir == a[rt].fir) {
      |               ^
weirdtree.cpp:130:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  130 |    for (auto [rt, lo, hi] : vec) if (fir == a[rt].fir) {
      |              ^
weirdtree.cpp: In member function 'int64_t SegmentTree::inspect(int, int)':
weirdtree.cpp:155:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  155 |   for (auto [rt, lo, hi] : vec) res += a[rt].tot;
      |             ^

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 10 / 10
• Subtask 6: 21 / 21
• Subtask 7: 29 / 29