Submission #1117438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117438		KK_1729	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1957 ms	122440 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;

// BeginCodeSnip{Lazy Segment Tree (from the module)}
template <class Info, class Tag> class LazySegtree {
  private:
	const int n;
	vector<Info> tree;
	vector<Tag> lazy;

	void build(int v, int l, int r, const vector<Info> &a) {
		if (l == r) {
			tree[v] = a[l];
		} else {
			int m = (l + r) >> 1;
			build(2 * v, l, m, a);
			build(2 * v + 1, m + 1, r, a);
			tree[v] = tree[2 * v] + tree[2 * v + 1];
		}
	}

	void apply(int v, int l, int r, const Tag &x) {
		tree[v].apply(x, l, r);
		lazy[v].apply(x);
	}

	void push_down(int v, int l, int r) {
		int m = (l + r) >> 1;
		apply(2 * v, l, m, lazy[v]);
		apply(2 * v + 1, m + 1, r, lazy[v]);
		lazy[v] = Tag();
	}

	void upd(int v, int l, int r, int ql, int qr, const Tag &x) {
		if (qr < l || ql > r) { return; }
		if (ql <= l && r <= qr) {
			apply(v, l, r, x);
		} else {
			push_down(v, l, r);
			int m = (l + r) >> 1;
			upd(2 * v, l, m, ql, qr, x);
			upd(2 * v + 1, m + 1, r, ql, qr, x);
			tree[v] = tree[2 * v] + tree[2 * v + 1];
		}
	}

	Info qry(int v, int l, int r, int ql, int qr) {
		if (qr < l || ql > r) { return Info(); }
		if (l >= ql && r <= qr) { return tree[v]; }
		push_down(v, l, r);
		int m = (l + r) >> 1;
		return qry(2 * v, l, m, ql, qr) + qry(2 * v + 1, m + 1, r, ql, qr);
	}

  public:
	LazySegtree(const vector<Info> &a) : n(a.size()) {
		tree.assign(4 << __lg(n), Info());
		lazy.assign(4 << __lg(n), Tag());
		build(1, 0, n - 1, a);
	}

	/** updates [ql, qr] with the arbitrary update chosen */
	void upd(int ql, int qr, const Tag &x) { upd(1, 0, n - 1, ql, qr, x); }

	/** @return result of range query on [ql, qr] */
	Info qry(int ql, int qr) { return qry(1, 0, n - 1, ql, qr); }
};
// EndCodeSnip

struct Tag {
	int added_val = -1;
	/** applies another lazy update to this update */
	void apply(const Tag &t) {
		if (t.added_val != -1) { added_val = t.added_val; }
	}
};

struct Info {
	int mx = -1;
	int applied = -1;
	/** applies an update to this tree node */
	void apply(const Tag &t, int l, int r) {
		if (t.added_val != -1) { applied = mx + t.added_val; }
	}
};

/** @return result of joining nodes a and b together */
Info operator+(const Info &a, const Info &b) {
	return {max(a.mx, b.mx), max(a.applied, b.applied)};
}

int main() {
	int n, q;
	cin >> n >> q;
	vector<int> w(n);
	for (int &i : w) { cin >> i; }

	vector<Info> arr(n);
	for (int i = 0; i < n; i++) {
		/*
		 * The default applied value (a.k.a. inversion pair value) must be
		 * initially set to 0, so that indices that aren't in an inversion pair
		 * will be effectively ignored by the segment tree.
		 */
		arr[i] = {w[i], 0};
	}
	LazySegtree<Info, Tag> st(arr);

	vector<vector<array<int, 3>>> tests(n);
	for (int i = 0; i < q; i++) {
		int l, r, k;
		cin >> l >> r >> k;
		l--, r--;
		tests[l].push_back({r, k, i});
	}

	vector<bool> res(q);
	stack<int> indices;
	for (int i = n - 1; i >= 0; i--) {
		// maintain a monotonic stack to find the first index j where w[i] >= w[j]
		while (!indices.empty() && w[indices.top()] < w[i]) { indices.pop(); }
		int b = indices.empty() ? n : indices.top();
		indices.push(i);
		st.upd(i + 1, b - 1, {w[i]});
		for (auto [r, k, idx] : tests[i]) { res[idx] = st.qry(i, r).applied <= k; }
	}

	for (int i = 0; i < q; i++) { cout << res[i] << '\n'; }
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23