Submission #887287

#	Time	Username	Problem	Language	Result	Execution time	Memory
887287		alex_2008	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1002 ms	108880 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;
struct query {
	int l;
	int r;
	int k;
	int ind;
};
bool cmp(query x, query y) {
	return x.l > y.l;
}
int a[N], l[N];
int b[N];
int tree[4 * N];
int ans[N];
void update(int v, int tl, int tr, int pos, int val) {
	if (tl == tr) {
		tree[v] = val;
		return;
	}
	int tm = (tl + tr) / 2;
	if (pos <= tm) {
		update(2 * v, tl, tm, pos, val);
	}
	else {
		update(2 * v + 1, tm + 1, tr, pos, val);
	}
	tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}
int MAX(int v, int tl, int tr, int l, int r) {
	if (tr < l || tl > r) return 0;
	if (tl >= l && tr <= r) return tree[v];
	int tm = (tl + tr) / 2;
	return max(MAX(2 * v, tl, tm, l, r),
		MAX(2 * v + 1, tm + 1, tr, l, r));
}
int main() {
 	ios_base::sync_with_stdio(false); cin.tie(0);
	int n, q;
	cin >> n >> q;
	a[0] = 1e9 + 10;
	vector <vector<int>> updates(n);
	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[l[i]].push_back(i);
	}
	vector <query> v;
	for (int i = 1; i <= q; i++) {
		int l, r, k;
		cin >> l >> r >> k;
		v.push_back({ l, r, k, i });
	}
	sort(v.begin(), v.end(), cmp);
	int prev_ind = n - 1;
	for (auto it : v) {
		int l = it.l, r = it.r, k = it.k, ind = it.ind;
		while (prev_ind >= l) {
			for (auto it : updates[prev_ind]) {
				update(1, 1, n, it, b[it]);
			}
			prev_ind--;
		}
		ans[ind] = (k >= MAX(1, 1, n, l, r))? 1: 0;
	}
	for (int i = 1; i <= q; i++) {
		cout << ans[i] << "\n";
	}
}

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