Submission #1143613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143613		crispxx	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	3094 ms	67832 KiB

sortbooks

/**
 *    author: a.k
 *    created: idk
**/
#include <bits/stdc++.h>
using namespace std;
 
#define all(x) x.begin(), x.end()
#define int long long
#define nl '\n'

const int INF = 1e9 + 1;

struct segtree {
	int n;
	vector<int> t;
	
	segtree(int n) : n(n), t(n << 2) {}
	
	void upd(int v, int tl, int tr, int i, int x) {
		if(tl == tr) {
			t[v] = x;
			return;
		}
		int tm = (tl + tr) >> 1;
		if(i <= tm) upd(v << 1, tl, tm, i, x);
		else upd(v << 1 | 1, tm + 1, tr, i, x);
		t[v] = max(t[v << 1], t[v << 1 | 1]);
	}
	void upd(int i, int x) {
		upd(1, 1, n, i, x);
	}
	int get(int v, int tl, int tr, int l, int r) {
		if(r < tl || tr < l) return 0;
		if(l <= tl && tr <= r) return t[v];
		int tm = (tl + tr) >> 1;
		int L = get(v << 1, tl, tm, l, r);
		int R = get(v << 1 | 1, tm + 1, tr, l, r);
		return max(L, R);
	}
	int get(int l, int r) {
		if(l > r) return 0;
		return get(1, 1, n, l, r);
	}
};

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m; cin >> n >> m;
	
	vector<int> a(n);
	
	for(auto &u : a) cin >> u;
	
	segtree t(n);
	
	while(m--) {
		int l, r, k; cin >> l >> r >> k;
		
		vector<pair<int, int>> v;
		
		for(int i = l; i <= r; i++) {
			v.emplace_back(a[i - 1], i);
			t.upd(i, a[i - 1]);
		}
		
		sort(all(v));
		
		bool flag = true;
		
		for(int i = (int)v.size() - 1; i >= 0; i--) {
			auto [u, idx] = v[i];
			if(u + t.get(idx + 1, r) > k) {
				flag = false;
				break;
			}
			t.upd(idx, -INF);
		}
		
		cout << flag << nl;
	}
}

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