Submission #1020963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020963		vjudge3	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	858 ms	75160 KiB

sortbooks

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

int a[1000005];
bool ans[1000005];
const int inf = 1e9;

struct Node {
	int ans, mx;
} seg[4000005];

struct Query {
	int id, l, r, k;
	bool operator< (Query& o) {return r < o.r;} 
};

int query_idx(int id, int l, int r, int x) {
	if (l == r) return l;
	if (seg[id*2+1].mx > x) return query_idx(id*2+1, (l+r)/2+1, r, x);
	return query_idx(id*2, l, (l+r)/2, x);
}

void upd_ans(int id, int l, int r, int pos, int x) {
	if (l == r) {
		seg[id].ans = max(seg[id].ans, x);
		return;
	}
	int mid = (l+r)/2;
	if (mid < pos) upd_ans(id*2+1, mid+1, r, pos, x);
	else upd_ans(id*2, l, mid, pos, x);
	seg[id].ans = max(seg[id*2].ans, seg[id*2+1].ans);
}

void upd_mx(int id, int l, int r, int pos, int x) {
	if (l == r) {
		seg[id].mx = x;
		return;
	}
	int mid = (l+r)/2;
	if (mid < pos) upd_mx(id*2+1, mid+1, r, pos, x);
	else upd_mx(id*2, l, mid, pos, x);
	seg[id].mx = max(seg[id*2].mx, seg[id*2+1].mx);
}

int query_ans(int id, int l, int r, int ql) {
	if (r < ql) return 0;
	if (ql <= l) return seg[id].ans;
	return max(query_ans(id*2, l, (l+r)/2, ql), query_ans(id*2+1, (l+r)/2+1, r, ql));
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	vector<Query> query (m);
	for (int i = 0; i < m; i++) {
		query[i].id = i+1;
		cin >> query[i].l >> query[i].r >> query[i].k;
	}
	query.push_back({0, 0, 0, 0});
	sort(query.begin(), query.end());
	for (int i = 1; i <= m; i++) {
		for (int j = query[i-1].r+1; j <= query[i].r; j++) {
			upd_mx(1, 1, n, j, a[j]);
			if (seg[1].mx != a[j]) {
				int idx = query_idx(1, 1, n, a[j]);
				upd_ans(1, 1, n, idx, a[idx] + a[j]);
			}
		}
		ans[query[i].id] = query_ans(1, 1, n, query[i].l) <= query[i].k;
	}
	for (int i = 1; i <= m; i++) cout << ans[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