oj.uz

Submission #798197

# Submission time Handle Problem Language Result Execution time Memory
798197 2023-07-30T13:17:23 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 541 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6+3, maxm = 1e6+3, maxw = 1e9+3;
int n, m;
int w[maxn];
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(-mxsum[v*2]);
		mxsum[v] = max({mxsum[v*2], mxsum[v*2+1], (it == els[v*2+1].end() ? -1 : mxsum[v*2] - *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;
	if (mid >= lb && mid+1 <= rb) {
		mxl = query2(l, mid, v*2, lb, mid);
		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];

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 188100 KB Output is correct
2 Correct 79 ms 188128 KB Output is correct
3 Incorrect 86 ms 188176 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 188100 KB Output is correct
2 Correct 79 ms 188128 KB Output is correct
3 Incorrect 86 ms 188176 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 271 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 541 ms 244436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 188100 KB Output is correct
2 Correct 79 ms 188128 KB Output is correct
3 Incorrect 86 ms 188176 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 188100 KB Output is correct
2 Correct 79 ms 188128 KB Output is correct
3 Incorrect 86 ms 188176 KB Output isn't correct
4 Halted 0 ms 0 KB -