oj.uz

Submission #503717

# Submission time Handle Problem Language Result Execution time Memory
503717 2022-01-08T17:25:11 Z atoiz Weirdtree (RMI21_weirdtree) C++14
100 / 100
 622 ms 31864 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 86 ms 8224 KB Output is correct
4 Correct 94 ms 8084 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 622 ms 31336 KB Output is correct
4 Correct 542 ms 31864 KB Output is correct
5 Correct 548 ms 30776 KB Output is correct
6 Correct 529 ms 30432 KB Output is correct
7 Correct 14 ms 8524 KB Output is correct
8 Correct 29 ms 8524 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8524 KB Output is correct
2 Correct 29 ms 8524 KB Output is correct
3 Correct 103 ms 29412 KB Output is correct
4 Correct 131 ms 30656 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 86 ms 8224 KB Output is correct
4 Correct 94 ms 8084 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 14 ms 8524 KB Output is correct
8 Correct 29 ms 8524 KB Output is correct
9 Correct 88 ms 8192 KB Output is correct
10 Correct 95 ms 7992 KB Output is correct
11 Correct 86 ms 7948 KB Output is correct
12 Correct 97 ms 8432 KB Output is correct
13 Correct 99 ms 8620 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 86 ms 8224 KB Output is correct
4 Correct 94 ms 8084 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 622 ms 31336 KB Output is correct
8 Correct 542 ms 31864 KB Output is correct
9 Correct 548 ms 30776 KB Output is correct
10 Correct 529 ms 30432 KB Output is correct
11 Correct 103 ms 29412 KB Output is correct
12 Correct 131 ms 30656 KB Output is correct
13 Correct 88 ms 8192 KB Output is correct
14 Correct 95 ms 7992 KB Output is correct
15 Correct 86 ms 7948 KB Output is correct
16 Correct 97 ms 8432 KB Output is correct
17 Correct 99 ms 8620 KB Output is correct
18 Correct 14 ms 8524 KB Output is correct
19 Correct 29 ms 8524 KB Output is correct
20 Correct 399 ms 28944 KB Output is correct
21 Correct 440 ms 30984 KB Output is correct
22 Correct 403 ms 30520 KB Output is correct
23 Correct 450 ms 30420 KB Output is correct
24 Correct 452 ms 29860 KB Output is correct