Submission #172127

#	Time	Username	Problem	Language	Result	Execution time	Memory
172127		Nordway	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1634 ms	82552 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> t, a;  

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() {
	ios_base::sync_with_stdio(NULL);
  	cin.tie(nullptr),cout.tie(nullptr);
	int n, m;
	cin >> n >> m;
	vector<int> inv(n, -1), ans(m);
	t.resize(4 * n);
	a.resize(n);
	vector<edge> q(m);
	for (int& x : a)
		cin >> x;
	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;
	}
	stack<int> s;
	for(int i = n - 1; i >= 0; i--){
  	 	while (!s.empty() && a[s.top()] < a[i]) {
  	 		inv[s.top()] = i;
  	 		s.pop();
  	 	}
  	 	s.push(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: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23