Submission #1280042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280042		jcelin	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	715 ms	71044 KiB

sortbooks

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 1e6 + 7;

int n, q;
int a[N], fen[N], l[N], r[N], k[N];
vector <int> qu[N];
bool res[N];

void add(int x, int y) {x = n-x-1; for (x++; x < N; x += x & -x) fen[x] = max(fen[x], y);}
int get(int x) {x = n-x-1; int out = 0; for (x++; x; x -= x & -x) out = max(out, fen[x]); return out;}

int main () {
	FIO;
	cin >> n >> q;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < q; i++) {
		cin >> l[i] >> r[i] >> k[i];
		l[i]--; r[i]--;
		qu[r[i]].pb(i);
	}
	
	vector <int> v;
	for (int i = 0; i < n; i++) {
		while (!v.empty() && a[v.back()] <= a[i]) v.pop_back();
		if (!v.empty()) {
			int x = v.back();
			add(x, a[i]+a[x]);
		}
		v.pb(i);
		for (int j : qu[i]) res[j] = (get(l[j]) <= k[j]);
	}
	
	for (int i = 0; i < q; i++) cout << res[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