Submission #342838

#	Time	Username	Problem	Language	Result	Execution time	Memory
342838		dimashii	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	30 / 100	581 ms	10312 KiB

sortbooks

#include <bits/stdc++.h>

#define fastio ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define ll long long

using namespace std;

const int mxN = 1e6 + 45, mod = 1e9 + 7;
const ll inf = 2e18 + 43;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m, w[mxN], p[mxN];

int main() {
	fastio;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) cin >> w[i];
	if (m <= 5000) {
		while (m--) {
			int l, r, k;
			cin >> l >> r >> k;
			int mx = w[l];
			bool bad = 0;
			for (int i = l + 1; i <= r; ++i) {
				if (mx > w[i] && mx + w[i] > k) {
					bad = 1;
					break;
				}
				mx = max(mx, w[i]);
			}
			cout << !bad << '\n';
		}
	}else {
		// should check is subarray sorted or not
		for (int i = 2; i <= n; ++i) p[i] = p[i - 1] + (w[i] >= w[i - 1]);
		while (m--) {
			int l, r, k;
			cin >> l >> r >> k;
			if (p[r] - p[l] == r - l) cout << "1\n";
			else cout << "0\n";
		}
	}
	return 0;
}

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