제출 #1094708

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1094708		stdfloat	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	77 / 100	3017 ms	43860 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++) {
		int mx = 0;
		for (int j = i * sz; j < min(n, (i + 1) * sz); j++) {
			if (a[j] < mx) v[i] = max(v[i], a[j] + mx);
			mx = max(mx, a[j]);
		}

		// cout << i << ' ' << v[i] << ' ' << i * sz << ' ' << min(n, (i + 1) * sz) - 1 << '\n';

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

	// cout << "sz " << sz << endl;

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

		if (l / sz == r / sz) {
			int mx = 0;
			bool tr = true;
			for (int i = l; i <= r && tr; i++) {
				tr = (a[i] >= mx || a[i] + mx <= k);
				mx = max(mx, a[i]);
			}
 
 			cout << tr << '\n';
 			continue;
		}

		int mx = 0;
		bool tr = true;
		for (int i = l; i < (l / sz + 1) * sz && tr; i++) {
			tr = (a[i] >= mx || a[i] + mx <= k);
			mx = max(mx, a[i]);
		}

		// cout << tr << ' ' << l << ' ' << (l / sz + 1) * sz << endl;

		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.begin() + y + 1, mx) : 0)) <= k);
			mx = max(mx, b[y]);
		}

		int x = r / sz * sz;
		for (int i = x; i <= r && tr; i++) {
			tr = (a[i] >= mx || a[i] + mx <= k);
			mx = max(mx, a[i]);
		}

		// cout << x << ' ' << mx << ' ' << mx2 << ' ' << tr << endl;

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

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