제출 #342014

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
342014		8e7	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2280 ms	49872 KiB

sortbooks

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <map>
#define ll long long
#define ff first
#define ss second
#define maxn 1000005
using namespace std;
struct segtree{
	int seg[4 * maxn];
	void modify(int cur, int l, int r, int ind, int val) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur] = max(seg[cur], val);
			//cout << l << " " << r << " " << val << endl;
			return;
		}
		int mid = (l + r) / 2;
		if (ind < mid) modify(cur * 2, l, mid, ind, val);
		else modify(cur * 2 + 1, mid, r, ind, val);
		seg[cur] = max(seg[cur * 2], seg[cur * 2 + 1]);
	}
	int query(int cur, int l, int r, int ql, int qr) {
		if (r <= l || ql >= r || qr <= l) return 0;
		if (ql <= l && qr >= r) return seg[cur];
		int mid = (l + r) / 2;
		return max(query(cur * 2, l, mid, ql, qr), query(cur * 2 + 1, mid, r, ql, qr));
	}
}ans, id;
struct query{
	int l = 0, r = 0, k = 0, id = 0;
} que[maxn];
inline bool cmp(query a, query b) {
	return a.r < b.r;
}
inline bool cmp2 (pair<int, int> a, pair<int, int> b) {
	return a.ss < b.ss;
}

int w[maxn];
vector<int> nums;
pair<int, int> mp[maxn];
bool ret[maxn];



int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1;i <= n;i++) {
		cin >> w[i];
		mp[i] = make_pair(w[i], i);
	}
	sort(mp + 1, mp + 1 + n);
	mp[1].ff = 1;
	int cur = 1;
	for (int i = 2;i <= n;i++) {
		if (w[mp[i].ss] > w[mp[i - 1].ss]) cur++;
		mp[i].ff = cur;
	}
	sort(mp + 1, mp + 1 + n, cmp2);

	for (int i = 0;i < m;i++) {
		cin >> que[i].l >> que[i].r >> que[i].k;
		que[i].id = i;
		que[i].r++;
	}
	sort(que, que + m, cmp);

	cur = 1;
	for (int i = 0;i < m;i++) {
		while (cur < que[i].r) {
			int upd = id.query(1, 0, n + 1, mp[cur].ff + 1, n + 1);
			ans.modify(1, 0, n + 1, upd, w[upd] + w[cur]);
			//cout << cur << " " << upd << " " << w[upd] + w[cur] << "\n";
			id.modify(1, 0, n + 1, mp[cur].ff, cur);
			//cout << cur << " " << mp[w[cur]] << endl;
			cur++;
		}
		int x = ans.query(1, 0, n + 1, que[i].l, que[i].r);
		//cerr << que[i].id << " " << x << endl;
		ret[que[i].id] = x <= que[i].k ? 1 : 0;
	}
	for (int i = 0;i < m;i++) cout << (ret[i] ? 1 : 0) << "\n";
}
/*
5 2
3 5 1 8 2
1 3 6
2 5 3
 */

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23