Submission #891247

#	Time	Username	Problem	Language	Result	Execution time	Memory
891247		serifefedartar	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	730 ms	95232 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 9;
const ll LOGN = 21;
const ll MAXN = 1e6 +  100;

struct Query {
	int l, r, k, id;
	Query(int _l, int _r, int _k, int _id) : l(_l), r(_r), k(_k), id(_id) { }
};

vector<Query> Q[MAXN];
int ans[MAXN], w[MAXN], fen[MAXN];
void update(int k, int val) {
	while (k) {
		fen[k] = max(fen[k], val);
		k -= k & -k;
	}
}

int get(int k) {
	int mx = 0;
	while (k < MAXN) {
		mx = max(mx, fen[k]);
		k += k & -k;
	}
	return mx;
}

int main() {
	fast
	int N, M, l, r, k;
	cin >> N >> M;

	w[0] = 1e9 + 100;
	for (int i = 1; i <= N; i++)
		cin >> w[i];
	for (int i = 0; i < M; i++) {
		cin >> l >> r >> k;
		Q[r].push_back(Query(l, r, k, i));
	}

	stack<int> st;
	st.push(0);
	for (int i = 1; i <= N; i++) {
		while (w[st.top()] <= w[i])
			st.pop();
		update(st.top(), w[st.top()] + w[i]);
		st.push(i);
		for (auto u : Q[i])
			ans[u.id] = get(u.l) <= u.k;
	}

	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