Submission #1094696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094696		stdfloat	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	3019 ms	42544 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()

#define ff  first
#define ss  second
#define pii pair<int, int>

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

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

	vector<int> a(n);
	for (auto &i : a)
		cin >> i;

	int sz = sqrt(n);
	while (sz * sz < n) sz++;
	while (sz * sz > n) sz--;

	vector<int> b = a, v((n - 1) / sz + 1);
	for (int i = 0; i < sz(v); i++) {
		set<int> s;
		for (int j = i * sz; j < min(n, (i + 1) * sz); j++) {
			if (!s.empty() && a[j] < *--s.end()) v[i] = max(v[i], a[j] + *s.upper_bound(a[j]));
			s.insert(a[j]);
		}

		sort(b.begin() + i * sz, b.begin() + min(n, (i + 1) * sz));
	}

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

		if (l / sz == r / sz) {
			set<int> s;
			bool tr = true;
			for (int i = l; i <= r && tr; i++) {
				tr = (s.empty() || a[i] >= *--s.end() || a[i] + *s.upper_bound(a[i]) <= k);
				s.insert(a[i]);
			}
 
 			cout << tr << '\n';
 			continue;
		}

		int mx = 0;
		set<int> s;
		bool tr = true;
		for (int i = l; i < (l / sz + 1) * sz && tr; i++) {
			mx = max(mx, a[i]);
			tr = (s.empty() || a[i] >= *--s.end() || a[i] + *s.upper_bound(a[i]) <= k);
			s.insert(a[i]);
		}

		if (!tr) {
			cout << "0\n";
			continue;
		}

		for (int i = l / sz + 1; i < r / sz && tr; i++) {
			int x = i * sz, y = (i + 1) * sz - 1;
			tr = (max(v[i], (mx > b[x] ? mx + *--lower_bound(b.begin() + x, b.end() + y + 1, mx) : 0)) <= k);
			mx = max(mx, b[y]);
		}

		int x = r / sz * sz;
		if (!tr || (mx > b[x] && mx + *--lower_bound(b.begin() + x, b.end() + r + 1, mx) > k)) {
			cout << "0\n";
			continue;
		}

		s.clear();
		for (int i = x; i <= r && tr; i++) {
			tr = (s.empty() || a[i] >= *--s.end() || a[i] + *s.upper_bound(a[i]) <= k);
			s.insert(a[i]);
		}

		cout << tr << '\n';
	}
}

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