제출 #798267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
798267		vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	34 / 100	1511 ms	216888 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5+3, maxm = 2e5+3, maxw = 1e9+3;
int n, m;
int w[maxn];
int mnw;
int mxsum[4*maxn];
set<int> els[4*maxn];

void build(int l, int r, int v) {
	if (l == r) {
		mxsum[v] = -1;
		els[v].insert(-w[l]);
	} else {
		int mid = (l+r)/2;
		build(l, mid, v*2);
		build(mid+1, r, v*2+1);
		auto it = els[v*2+1].upper_bound(*els[v*2].begin());
		mxsum[v] = max({mxsum[v*2], mxsum[v*2+1], (it == els[v*2+1].end() ? -1 : -*els[v*2].begin() - *it)});
		for (int x : els[v*2]) els[v].insert(x);
		for (int x : els[v*2+1]) els[v].insert(x);
	}
}

int query2(int l, int r, int v, int lb, int rb) {
	if (r < lb || l > rb) return -1;
	if (l >= lb && r <= rb) return -*els[v].begin();
	int mid = (l+r)/2;
	return max(query2(l, mid, v*2, lb, rb), query2(mid+1, r, v*2+1, lb, rb));
}

int query3(int l, int r, int v, int lb, int rb, int k) {
	if (r < lb || l > rb) return -1;
	if (l >= lb && r <= rb) {
		auto it = els[v].upper_bound(-k);
		return (it == els[v].end() ? -1 : -*it);
	}
	int mid = (l+r)/2;
	return max(query3(l, mid, v*2, lb, rb, k), query3(mid+1, r, v*2+1, lb, rb, k));
}

int query1(int l, int r, int v, int lb, int rb) {
	if (r < lb || l > rb) return -1;
	if (l >= lb && r <= rb) return mxsum[v];
	int mid = (l+r)/2;
	int mxl = -1, mxr = -1;
	mxl = query2(l, mid, v*2, lb, mid);
	if (mxl != -1) mxr = query3(mid+1, r, v*2+1, mid+1, rb, mxl);
	return max({
		query1(l, mid, v*2, lb, rb),
		query1(mid+1, r, v*2+1, lb, rb),
		(mxr == -1 ? -1 : mxl + mxr)
	});
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for (int i=0; i<n; i++) cin >> w[i];

	mnw = 1e9+3;
	for (int i=0; i<n; i++) mnw = min(mnw, w[i]);

	build(0, n-1, 1);

	// for (int i=0; i<n; i++) {
	// 	for (int j=i; j<n; j++) {
	// 		cout << i << ' ' << j << ' ' << query1(0, n-1, 1, i, j) << '\n';
	// 	}
	// }

	while (m--) {
		int l, r, k;
		cin >> l >> r >> k;
		if (k < mnw) cout << (l == r) << '\n';
		else cout << (query1(0, n-1, 1, l-1, r-1) <= k) << '\n';
	}
	return 0;
}

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