Submission #500771

#	Time	Username	Problem	Language	Result	Execution time	Memory
500771		Mazaalai	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	64 / 100	3033 ms	262144 KiB

sortbooks

#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define LINE "----------------------\n"
#define ALL(x) x.begin(),x.end()
using namespace std;
using ll = long long;
using PII = pair <int, int>;
using VI = vector <int>;
using VVI = vector <VI>;
using VPI = vector <PII>;

const int N = 1e6 + 5;
const int M = 4 * N;
int nums[N];
struct Node {
	int maxInv;
	vector <int> vals;
	Node() {
		maxInv = -1;
	}
	void init(int l, int r) {
		int curMax = nums[l];
		vals.pb(nums[l]);
		for (int i = l+1; i <= r; i++) {
			vals.pb(nums[i]);
			if (nums[i] >= curMax) curMax = nums[i];
			else maxInv = max(maxInv, curMax+nums[i]);
		}
		sort(ALL(vals));
	}
	int findSmaller(int x) {
		int id = lower_bound(ALL(vals), x) - vals.begin();
		return (id ? vals[id-1] : -1);
	}
};
Node node[M];
int n, m;
void build(int l, int r, int head) {
	node[head].init(l, r);
	if (l == r) return;
	int mid = (l+r)>>1;
	build(l, mid, head*2+1);
	build(mid+1, r, head*2+2);
}
PII zero = {-1, -1};
int maxQuery(int l, int r, int L, int R, int mx, int head) { // returns MaxInv, ans maxEl
	if (l > R || L > r) return -1;
	if (L <= l && r <= R) return node[head].findSmaller(mx);
	int mid = (l+r)>>1;
	return max(
		maxQuery(l, mid, L, R, mx, head*2+1),
		maxQuery(mid+1, r, L, R, mx, head*2+2)
	);
}
PII query(int l, int r, int L, int R, int head) { // returns MaxInv, ans maxEl
	if (l > R || L > r) return zero;
	if (L <= l && r <= R) return {node[head].maxInv, node[head].vals.back()};
	int mid = (l+r)>>1;
	PII lhs = query(l, mid, L, R, head*2+1);
	PII rhs = query(mid+1, r, L, R, head*2+2);
	int maxAns = max(lhs.ff, rhs.ff);
	if (lhs.ss != -1) {
		int mx = maxQuery(mid+1, r, L, R, lhs.ss, head*2+2);
		// int mx = node[head*2+2].findSmaller(lhs.ss);
		if (mx != -1) maxAns = max(maxAns, lhs.ss + mx);
	}
	return {maxAns, max(lhs.ss, rhs.ss)};
}
signed main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> nums[i];
	build(1, n, 0);
	for (int i = 0; i < m; i++) {
		int l, r, k; cin >> l >> r >> k;
		// cout << LINE;
		int cur = query(1, n, l, r, 0).ff;
		// cout << l << ' ' << r << ' ' << cur << '\n';
		cout << (cur > k ? 0 : 1) << "\n";
	}

}

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