Submission #272381

#	Time	Username	Problem	Language	Result	Execution time	Memory
272381		aZvezda	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	3071 ms	215872 KiB

sortbooks

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

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

struct Node : vector<int> {
	int mxSum;
	Node() : vector<int>(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));
	//unique(ret.begin(), ret.end());
	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[2 * MAX_N];

void build(int curr, int l, int r) {
	//cout << curr << " " << l << " " << r << endl;
	if(l == r) {
		//cout << "1" << endl;
		int a;
		cin >> a;
		tree[curr].push_back(a);
		//cout << 2 << endl;
		return;
	}
	//cout << curr << " " << l << " " << r << endl;
	int m = (l + r) / 2;
	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;
}

void build(int n) {
	for(int i = MAX_N; i < MAX_N + n; i ++) {
		int a;
		cin >> a;
		tree[i].push_back(a);
	}
	for(int i = MAX_N + n; i < 2 * MAX_N; i ++) {
		tree[i].push_back(mod);
	}
	for(int i = MAX_N - 1; i > 0; i --) {
		tree[i] = tree[i * 2] + tree[i * 2 + 1];
	}
	//cout << "Here" << endl;
}

int query(int l, int r) {
	l += MAX_N; r += MAX_N + 1;
	vector<int> lft, rgt;
	while(l < r) {
		if(l & 1) {lft.push_back(l); l ++;}
		if(r & 1) {r --; rgt.push_back(r);}
		l /= 2;
		r /= 2;
	}
	for(auto it : rgt) {
		lft.push_back(it);
	}
	int mx = -1;
	int ret = 0;
	for(auto it : lft) {
		chkmax(ret, tree[it].mxSum);
		auto now = lower_bound(tree[it].begin(), tree[it].end(), mx);
		if(now != tree[it].begin()) {
			now --;
			chkmax(ret, mx + (*now)) ;
		}
		chkmax(mx, tree[it].back());
	}
	return ret;
}

pair<int, int> getMaxInvSum(int curr, int l, int r, int ql, int qr, int 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 {-mod, -mod};
	}
	int m = (l + r) / 2;
	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<int, int> 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);
	int n;
	cin >> n;
	int q;
	cin >> q;
	build(n);
	while(q --) {
		int l, r, k;
		cin >> l >> r >> k;
		cout << (query(l - 1, r - 1) <= k) << endl;
		//cout << l << " " << r << " " << k << endl;
	}
}
 

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