Submission #271447

#	Time	Username	Problem	Language	Result	Execution time	Memory
271447		aZvezda	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	64 / 100	955 ms	262148 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
typedef unsigned long long ull;
template<class T, class T2> bool chkmax(T &a, const T2 &b) {return (a < b) ? a = b, 1 : 0;}

const ll mod = 1e9 + 7;
const ll MAX_N = 1e6 + 10;

struct Node : vector<ll> {
	ll mxSum;
	Node() : vector<ll>(0), mxSum(0) {}
};

Node operator +(const Node &a, const Node &b) {
	Node ret;
	//cout << "Merging " << endl;
	merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(ret));
	auto curr = lower_bound(b.begin(), b.end(), a.back());
	if(curr == b.begin()) {
		ret.mxSum = 0;
	} else {
		curr --;
		ret.mxSum = a.back() + (*curr);
	}
	chkmax(ret.mxSum, max(a.mxSum, b.mxSum));
	return ret;
}

Node tree[4 * MAX_N];
ll arr[MAX_N];

void build(ll curr, ll l, ll r) {
	//cout << curr << " " << l << " " << r << endl;
	if(l == r) {
		//cout << "1" << endl;
		tree[curr].push_back(arr[l]);
		//cout << 2 << endl;
		return;
	}
	//cout << curr << " " << l << " " << r << endl;
	ll m = (l + r) / 2ll;
	build(curr * 2, l, m);
	build(curr * 2 + 1, m + 1, r);
	//cout << curr << "!! " << l << " " << r << endl;
	tree[curr] = tree[curr * 2] + tree[curr * 2 + 1];
	//cout << curr << "! " << l << " " << r << endl;
}

pair<ll, ll> getMaxInvSum(ll curr, ll l, ll r, ll ql, ll qr, ll got) {
	if(ql <= l && r <= qr) {
		auto now = lower_bound(tree[curr].begin(), tree[curr].end(), got);
		if(now == tree[curr].begin()) {
			return {tree[curr].mxSum, tree[curr].back()};
		} else {
			now --;
			return {max(tree[curr].mxSum, got + (*now)), tree[curr].back()};
		}
	} else if(l > qr || r < ql) {
		return {0, 0};
	}
	ll m = (l + r) / 2ll;
	auto retr = getMaxInvSum(curr * 2, l, m, ql, qr, got);
	auto retl = getMaxInvSum(curr * 2 + 1, m + 1, r, ql, qr, max(got, retr.second));
	pair<ll, ll> ret;
	ret.first = max(retr.first, retl.first);
	ret.second = max(retr.second, retl.second);
	return ret;
} 

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	ll n;
	cin >> n;
	ll q;
	cin >> q;
	for(ll i = 0; i < n; i ++) {
		cin >> arr[i];
	}
	build(1, 0, n - 1);
	//cout << "Here" << endl;
	while(q --) {
		ll l, r, k;
		cin >> l >> r >> k;
		cout << (getMaxInvSum(1, 0, n - 1, l - 1, r - 1, 0).first <= k) << endl;
		//cout << l << " " << r << " " << k << endl;
	}
}
 

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