Submission #498966

#	Time	Username	Problem	Language	Result	Execution time	Memory
498966		NachoLibre	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	749 ms	78816 KiB

sortbooks

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;

const int inf = 2e9;

vector<int> f;
void upd(int i, int x) {
	for(; i < sz(f); i += (i & -i)) {
		f[i] = max(f[i], x);
	}
}

int maxx(int i) {
	int x = 0;
	for(; i; i -= (i & -i)) {
		x = max(x, f[i]);
	}
	return x;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	f = vector<int>(n + 1, 0);
	int a[n + 1], b[n + 1];
	memset(b, 0, sizeof b);
	vector<pair<int, int> > v(1, {inf, 0});
	vector<int> u[n + 1];
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		while(v.back().first <= a[i]) { v.pop_back(); }
		b[i] = v.back().second;
		v.push_back({a[i], i});
		u[b[i]].push_back(i);
	}
	vector<array<int, 4> > q;
	for(int i = 1; i <= m; ++i) {
		int l, r, k;
		cin >> l >> r >> k;
		q.push_back({l, r, k, i});
	}
	sort(all(q));
	reverse(all(q));
	int on = n + 1;
	int fp[m + 1];
	for(auto x : q) {
		while(on > x[0]) {
			on -= 1;
			for(int i : u[on]) {
				upd(i, a[on] + a[i]);
			}
		}
		fp[x[3]] = x[2] >= maxx(x[1]);
	}
	for(int i = 1; i <= m; ++i) {
		cout << fp[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