Submission #1293142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293142		youneverfindeme	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	958 ms	76520 KiB

sortbooks

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


typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define len(x) (int)(x).size()
#define All(x) (x).begin(),(x).end()
#define pb push_back

const int N = 1e6 + 7;
int n, r[N], a[N], ans[N], seg[N << 2], lazy[N << 2];
vector<pair<int, pii>> vec[N];

void Apply(int id, int x) {
	seg[id] = max(seg[id], x);
	lazy[id] = max(lazy[id], x);
}

void shift(int id) {
	for (int v: {id << 1, id << 1 | 1})
		Apply(v, lazy[id]);
	lazy[id] = 0;
}

void upd(int l, int r, int x, int id = 1, int st = 0, int en = n) {
	if (r <= st || l >= en)
		return;
	if (st >= l && en <= r) {
		Apply(id, x);
		return;
	}
	shift(id);
	int mid = (st + en) >> 1;
	upd(l, r, x, id << 1, st, mid);
	upd(l, r, x, id << 1 | 1, mid, en);
	seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
}

int get(int p, int id = 1, int st = 0, int en = n) {
	if (en - st == 1)
		return seg[id];
	int mid = (st + en) >> 1;
	shift(id);
	if (p < mid)
		return get(p, id << 1, st, mid);;
	return get(p, id << 1 | 1, mid, en);
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int q;
	cin >> n >> q;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < q; i++) {
		int l, r, x;
		cin >> l >> r >> x;
		vec[--l].pb({i, {--r, x}});
	}
	for (int i = n - 1; i >= 0; i--) {
		r[i] = i + 1;
		while (r[i] < n && a[r[i]] < a[i]) {
			upd(r[i], n, a[i] + a[r[i]]);
			r[i] = r[r[i]];
		}
		for (auto x: vec[i]) {
			int id = x.F;
			int r = x.S.F;
			int k = x.S.S;
			int t = get(r);
		//	cout << "****" << i + 1 << ' ' << r + 1 << ' ' << t << '\n';
			ans[id] = t <= k;
		}
	}
	for (int i = 0; i < q; i++)
		cout << ans[i] << '\n';
    return 0;
}

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