Submission #270122

#	Time	Username	Problem	Language	Result	Execution time	Memory
270122		aZvezda	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	8 / 100	3064 ms	14712 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 = 1e5 + 10;

pair<ll, ll> tree[4 * MAX_N];
ll arr[MAX_N];

pair<ll, ll> operator +(const pair<ll, ll> &a, const pair<ll, ll> &b) {
	return {min(a.first, b.first), max(a.first, b.first)};
}

void build(ll curr, ll l, ll r) {
	if(l == r) {
		tree[curr] = {arr[l], arr[l]};
		return;
	}
	ll m = (l + r) / 2ll;
	build(curr * 2, l, m);
	build(curr * 2 + 1, m + 1, r);
	tree[curr] = tree[curr * 2] + tree[curr * 2 + 1];
}

ll queryMin(ll curr, ll l, ll r, ll ql, ll qr) {
	if(ql <= l && r <= qr) {
		return tree[curr].first;
	} else if(l > qr || r < ql) {
		return mod;
	}
	ll m = (l + r) / 2ll;
	return min(queryMin(curr * 2, l, m, ql, qr), queryMin(curr * 2 + 1, m + 1, r, ql, qr));
}

ll queryMax(ll curr, ll l, ll r, ll ql, ll qr) {
	if(ql <= l && r <= qr) {
		return tree[curr].second;
	} else if(l > qr || r < ql) {
		return -mod;
	}
	ll m = (l + r) / 2ll;
	return max(queryMax(curr * 2, l, m, ql, qr), queryMax(curr * 2 + 1, m + 1, r, ql, qr));
}

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];
	}
	while(q --) {
		int l, r, k;
		cin >> l >> r >> k;
		l --; r --;
		int mx = -mod;
		for(int i = l; i <= r; i ++) {
			for(int j = i + 1; j <= r; j ++) {
				if(arr[i] > arr[j]) {
					chkmax(mx, arr[i] + arr[j]);
				}
			}
		}
		//cout << mn << " " << arr[bad] << " " << k << endl;
		cout << (mx <= k) << endl;
	}
	return 0;
	build(1, 0, n - 1);
	while(q --) {
		ll l, r, k;
		cin >> l >> r >> k;
		//cout << l << " " << r << " " << k << endl;
		l --; r --;
		while(r >= l) {
			if(queryMax(1, 0, n - 1, l, r) == arr[r]) {
				r --;
			} else {
				break;
			}
		}
		if(r < l) {
			cout << 1 << endl;
		} else if(queryMin(1, 0, n - 1, l, r) + queryMax(1, 0, n - 1, l, r) <= k) {
			cout << 1 << endl;
		} else {
			cout << 0 << endl;
		}
	}
}
 

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