Submission #887280

#	Time	Username	Problem	Language	Result	Execution time	Memory
887280		alex_2008	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	64 / 100	674 ms	262144 KiB

sortbooks

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#include <bitset>
typedef long long ll;
using namespace std;
const int N = 1e6 + 10;
int sz = 0;
struct Node {
	int left;
	int right;
	int mx;
};
int a[N], l[N];
int b[N];
int root[N];
Node tree[30 * N];
void build_tree(int v, int tl, int tr) {
	tree[v].left = 0;
	tree[v].right = 0;
	tree[v].mx = 0;
	if (tl != tr) {
		tree[v].left = ++sz;
		tree[v].right = ++sz;
		int tm = (tl + tr) / 2;
		build_tree(tree[v].left, tl, tm);
		build_tree(tree[v].right, tm + 1, tr);
	}
}
void update(int v, int prev_v, int tl, int tr, int pos, int val) {
	if (tl == tr) {
		tree[v].mx = val;
		return;
	}
	int tm = (tl + tr) / 2;
	if (pos <= tm) {
		tree[v].right = tree[prev_v].right;
		tree[v].left = ++sz;
		update(tree[v].left, tree[prev_v].left, tl, tm, pos, val);
	}
	else {
		tree[v].left = tree[prev_v].left;
		tree[v].right = ++sz;
		update(tree[v].right, tree[prev_v].right, tm + 1, tr, pos, val);
	}
	tree[v].mx = max(tree[tree[v].left].mx, tree[tree[v].right].mx);
}
int MAX(int v, int tl, int tr, int l, int r) {
	if (tl > r || tr < l) return 0;
	if (tl >= l && tr <= r) return tree[v].mx;
	int tm = (tl + tr) / 2;
	return max(MAX(tree[v].left, tl, tm, l, r), MAX(tree[v].right, tm + 1, tr, l, r));
}
int main() {
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= 24 * n; i++) {
		tree[i] = { 0, 0, 0 };
	}
	a[0] = 1e9 + 10;
	vector <pair<int, int>> updates;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		l[i] = i - 1;
		while (a[i] >= a[l[i]]) {
			l[i] = l[l[i]];
		}
		b[i] = a[i] + a[l[i]];
		updates.push_back({ l[i], i });
	}
	updates.push_back({ n, 0 });
	sort(updates.begin(), updates.end());
	root[n] = ++sz;
	build_tree(root[n], 1, n);
	for (int i = n - 1; i >= 0; i--) {
		root[i] = ++sz;
		update(root[i], root[i + 1], 1, n, updates[i].second, b[updates[i].second]);
	}
	while (q--) {
		int l, r, k;
		cin >> l >> r >> k;
		int ind = lower_bound(updates.begin(), updates.end(), make_pair(l, 0)) - updates.begin();
		if (MAX(root[ind], 1, n, l, r) <= k) cout << 1 << "\n";
		else cout << 0 << "\n";
	}
}

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