Submission #500878

#	Time	Username	Problem	Language	Result	Execution time	Memory
500878		Mazaalai	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1157 ms	75240 KiB

sortbooks

#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define LINE "----------------------\n"
#define ALL(x) x.begin(),x.end()
using namespace std;
using ll = long long;
using PII = pair <int, int>;
using VI = vector <int>;
using VVI = vector <VI>;
using VPI = vector <PII>;

const int N = 1e6 + 5;
const int M = 4 * N;
const int INF = 1e9+1;
int nums[N], ans[N], node[M];
int n, m;
struct Query {
	int l, r, k, id;
	Query () {}
	Query (int _l, int _r, int _k, int _id) {
		l = _l;
		r = _r;
		k = _k;
		id = _id;
	}
	void init (int _l, int _r, int _k, int _id) {
		l = _l;
		r = _r;
		k = _k;
		id = _id;
	}
	bool operator < (const Query& a) const {
		return r < a.r;
	}
};
void update(int l, int r, int id, int val, int head) {
	if (l == r) {
		node[head] = val;
		return;
	}
	int mid = (l+r)>>1;
	if (id <= mid) update(l, mid, id, val, head*2+1);
	else update(mid+1, r, id, val, head*2+2);
	node[head] = max(node[head*2+1], node[head*2+2]);
}
int query(int l, int r, int L, int R, int head) {
	if (l > R || L > r) return -1;
	if (L <= l && r <= R) return node[head];
	int mid = (l+r)>>1;
	return max(
		query(l, mid, L, R, head*2+1),
		query(mid+1, r, L, R, head*2+2)
	);
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	cin >> n >> m;
	nums[0] = 1e9+1;
	for (int i = 1; i <= n; i++) cin >> nums[i];
	vector <Query> queries;
	Query tmp;
	for (int i = 1; i <= m; i++) {
		int l, r, k; cin >> l >> r >> k;
		tmp.init(l, r, k, i);
		queries.pb(tmp);
	}
	sort(ALL(queries));
	stack <int> stk;
	stk.push(0);
	memset(node, -1, sizeof(node));
	for (int i = 1, j = 0; i <= n && j < m; i++) {
		while (nums[i] >= nums[stk.top()]) stk.pop();
		if (stk.size() > 1) update(1, n, stk.top(), nums[stk.top()]+nums[i], 0);
		stk.push(i);
		while (queries[j].r == i) {
			ans[queries[j].id] = (query(1, n, queries[j].l, queries[j].r, 0) > queries[j].k ? 0 : 1);
			// cout << "add: " << queries[j].l << ' ' << queries[j].r << ' ' << query(1, n, queries[j].l, queries[j].r, 0) << '\n';
			j++;
		}
	}
	for (int i = 1; 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