Submission #1242794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242794		ssitaram	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	34 / 100	3096 ms	59792 KiB

sortbooks

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

typedef long long ll;
typedef long double ld;

struct segtree {
	int n;
	vector<int> val;

	segtree(int sz) {
		n = 1;
		while (n < sz) n *= 2;
		val.resize(2 * n - 1);
	}

	void upd(int node, int l, int r, int i, int v) {
		if (r == l + 1) {
			val[node] = v;
			return;
		}
		int m = (l + r) / 2;
		if (i < m) upd(node * 2 + 1, l, m, i, v);
		else upd(node * 2 + 2, m, r, i, v);
		val[node] = max(val[node * 2 + 1], val[node * 2 + 2]);
	}

	void upd(int i, int v) {
		upd(0, 0, n, i, v);
	}

	int mx(int node, int l, int r, int a, int b) {
		if (r <= a || l >= b) return 0;
		if (a <= l && r <= b) return val[node];
		int m = (l + r) / 2;
		return max(mx(node * 2 + 1, l, m, a, b), mx(node * 2 + 2, m, r, a, b));
	}

	int mx(int a, int b) {
		return mx(0, 0, n, a, b);
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m; cin >> n >> m;
	vector<int> w(n);
	for (int& i : w) cin >> i;
	vector<bool> ans(m);
	vector<vector<pair<int, pair<int, int>>>> qs(n);
	for (int i = 0; i < m; ++i) {
		int l, r, w; cin >> l >> r >> w;
		qs[--r].push_back({--l, {w, i}});
	}
	segtree at(n);
	for (int i = 0; i < n; ++i) {
		for (int j = i - 1; j >= 0; --j) {
			if (w[j] > w[i]) {
				at.upd(j, w[j] + w[i]);
				break;
			}
		}
		for (pair<int, pair<int, int>>& j : qs[i]) {
			ans[j.second.second] = (at.mx(j.first, i + 1) <= j.second.first);
		}
	}
	for (int i = 0; i < m; ++i) {
		cout << ans[i] << '\n';
	}
	return 0;
}

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