Submission #172113

#	Time	Username	Problem	Language	Result	Execution time	Memory
172113		Nordway	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	3018 ms	63764 KiB

sortbooks

#include<bits/stdc++.h>

using namespace std;

struct edge {
	int l;
	int r;
	int k;
	int id;
};
bool cmp(edge l, edge r) {
 	return (l.r <= r.r);
}
vector<int> s, t, a;

void build(int u, int l, int r) {
 	if (r - l == 1) {
 	 	s[u] = a[l];
 	 	return;
 	}
 	int m = (l + r) / 2;
 	build(u + u + 1, l, m);
 	build(u + u + 2, m, r);
 	s[u] = max(s[u + u + 1], s[u + u + 2]);
}
int position(int u, int l, int r, int x, int val) {
	if (l >= x || s[u] <= val)
		return -1;
	if (r - l == 1)
		return l;
	int m = (l + r) / 2;
	int pos = position(u + u + 2, m, r, x, val);
	if (pos == -1)
		pos = position(u + u + 1, l, m, x, val);
	return pos;
}             

void upd(int u, int l, int r, int pos, int val) {
 	if (r - l == 1) {
		t[u] = max(t[u], val);
		return;
 	}
 	int m = (l + r) / 2;
 	if (pos < m) upd(u + u + 1, l, m, pos, val);
 	else upd(u + u + 2, m, r, pos, val);
 	t[u] = max(t[u + u + 1], t[u + u + 2]);
}

int get(int u, int ul, int ur, int l, int r) {
 	if (ul >= r || l >= ur)
 		return 0;
 	if (l <= ul && ur <= r)
 		return t[u];
 	int um = (ul + ur) / 2;
 	return max(get(u + u + 1, ul, um, l, r), get(u + u + 2, um, ur, l, r));
}

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> inv(n), ans(m);
	t.resize(4 * n), s = t;
	a.resize(n);
	vector<edge> q(m);
	for (int& x : a)
		cin >> x;
	build(0, 0, n);
	for (int i = 0; i < m; i++) {
	 	int l, r, x;
	 	cin >> l >> r >> x;
	 	l--, r--;
	 	q[i].l = l;
	 	q[i].r = r;
	 	q[i].id = i;
	 	q[i].k = x;
	}
	for (int i = 0; i < n; i++) 
	 	inv[i] = position(0, 0, n, i, a[i]);
	sort(q.begin(), q.end(), cmp);
	int pos = 0;
	for (int i = 0; i < n; i++) {
		if (inv[i] != -1) {
		 	upd(0, 0, n, inv[i], a[i] + a[inv[i]]);
		}
		while (pos < m && i == q[pos].r) {
			ans[q[pos].id] = (get(0, 0, n, q[pos].l, q[pos].r + 1) <= q[pos].k);
			pos++;
		}                	
	}
	for (int i = 0; i < m; i++)
		cout << ans[i] << "\n";
}

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