Submission #1096192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096192		stdfloat	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	2599 ms	262144 KiB

sortbooks

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

using ll = long long;

#define sz(v)  (int)(v).size()
#define all(v) (v).begin(), v.end()

int mx;

vector<int> a, st, vis;

vector<vector<int>> v;

void bld(int nd, int l, int r) {
	if (l == r) {
		vis[nd] = 0; st[nd] = a[l]; v[nd] = {a[l]};
		return;
	}

	int ch = (nd << 1) + 1, md = l + r >> 1;
	bld(ch, l, md); bld(ch + 1, md + 1, r);

	st[nd] = max(st[ch], st[ch + 1]);

	v[nd].assign(sz(v[ch]) + sz(v[ch + 1]), 0);
	merge(all(v[ch]), all(v[ch + 1]), v[nd].begin());
	
	int mx = 0;
	for (int i = l; i <= r; i++) {
		if (mx > a[i]) vis[nd] = max(vis[nd], mx + a[i]);
		else mx = a[i];
	}
}

bool fnd(int nd, int l, int r, int x, int y, int k) {
	if (r < x || y < l) return true;

	if (x <= l && r <= y) {
		bool tr = (max(vis[nd], (mx > v[nd][0] ? mx + *--lower_bound(all(v[nd]), mx) : 0)) <= k);
		mx = max(mx, st[nd]);
		return tr;
	}

	int ch = (nd << 1) + 1, md = l + r >> 1;
	return (!fnd(ch, l, md, x, y, k) || !fnd(ch + 1, md + 1, r, x, y, k) ? false : true);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n, q;
	cin >> n >> q;

	a.assign(n, 0);
	for (auto &i : a)
		cin >> i;

	v.assign(n << 2, {});
	st = vis = vector<int>(n << 2);
	bld(0, 0, n - 1);

	while (q--) {
		int l, r, k;
		cin >> l >> r >> k; l--; r--;

		mx = 0;
		cout << fnd(0, 0, n - 1, l, r, k) << endl;
	}
}

Compilation message (stderr)

sortbooks.cpp: In function 'void bld(int, int, int)':
sortbooks.cpp:21:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |  int ch = (nd << 1) + 1, md = l + r >> 1;
      |                               ~~^~~
sortbooks.cpp: In function 'bool fnd(int, int, int, int, int, int)':
sortbooks.cpp:45:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |  int ch = (nd << 1) + 1, md = l + r >> 1;
      |                               ~~^~~

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