oj.uz

Submission #798258

# Submission time Handle Problem Language Result Execution time Memory
798258 2023-07-30T14:26:16 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 1824 ms 223252 KB 
#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 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];

	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;
		cout << (query1(0, n-1, 1, l-1, r-1) <= k) << '\n';
	}
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37900 KB Output is correct
2 Correct 17 ms 37828 KB Output is correct
3 Correct 21 ms 37876 KB Output is correct
4 Correct 17 ms 37908 KB Output is correct
5 Correct 18 ms 37876 KB Output is correct
6 Correct 19 ms 38148 KB Output is correct
7 Correct 19 ms 38088 KB Output is correct
8 Correct 19 ms 38152 KB Output is correct
9 Correct 19 ms 37972 KB Output is correct
10 Correct 18 ms 37968 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37900 KB Output is correct
2 Correct 17 ms 37828 KB Output is correct
3 Correct 21 ms 37876 KB Output is correct
4 Correct 17 ms 37908 KB Output is correct
5 Correct 18 ms 37876 KB Output is correct
6 Correct 19 ms 38148 KB Output is correct
7 Correct 19 ms 38088 KB Output is correct
8 Correct 19 ms 38152 KB Output is correct
9 Correct 19 ms 37972 KB Output is correct
10 Correct 18 ms 37968 KB Output is correct
11 Correct 23 ms 38756 KB Output is correct
12 Correct 30 ms 41124 KB Output is correct
13 Correct 30 ms 41084 KB Output is correct
14 Correct 34 ms 41268 KB Output is correct
15 Correct 34 ms 41244 KB Output is correct
16 Correct 32 ms 41100 KB Output is correct
17 Correct 27 ms 40564 KB Output is correct
18 Correct 23 ms 38516 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 64 ms 80300 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 92008 KB Output is correct
2 Correct 451 ms 92156 KB Output is correct
3 Correct 300 ms 49900 KB Output is correct
4 Correct 291 ms 49808 KB Output is correct
5 Correct 280 ms 50000 KB Output is correct
6 Correct 299 ms 49808 KB Output is correct
7 Correct 284 ms 49872 KB Output is correct
8 Correct 229 ms 49100 KB Output is correct
9 Correct 84 ms 38504 KB Output is correct
10 Correct 193 ms 49140 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37900 KB Output is correct
2 Correct 17 ms 37828 KB Output is correct
3 Correct 21 ms 37876 KB Output is correct
4 Correct 17 ms 37908 KB Output is correct
5 Correct 18 ms 37876 KB Output is correct
6 Correct 19 ms 38148 KB Output is correct
7 Correct 19 ms 38088 KB Output is correct
8 Correct 19 ms 38152 KB Output is correct
9 Correct 19 ms 37972 KB Output is correct
10 Correct 18 ms 37968 KB Output is correct
11 Correct 23 ms 38756 KB Output is correct
12 Correct 30 ms 41124 KB Output is correct
13 Correct 30 ms 41084 KB Output is correct
14 Correct 34 ms 41268 KB Output is correct
15 Correct 34 ms 41244 KB Output is correct
16 Correct 32 ms 41100 KB Output is correct
17 Correct 27 ms 40564 KB Output is correct
18 Correct 23 ms 38516 KB Output is correct
19 Correct 1510 ms 223176 KB Output is correct
20 Correct 1506 ms 223236 KB Output is correct
21 Correct 1280 ms 223032 KB Output is correct
22 Correct 1211 ms 223116 KB Output is correct
23 Correct 1281 ms 223112 KB Output is correct
24 Correct 1419 ms 222992 KB Output is correct
25 Correct 1434 ms 223044 KB Output is correct
26 Correct 1681 ms 223176 KB Output is correct
27 Correct 1638 ms 223080 KB Output is correct
28 Correct 1756 ms 223152 KB Output is correct
29 Correct 1773 ms 223252 KB Output is correct
30 Correct 1769 ms 223168 KB Output is correct
31 Correct 1819 ms 223192 KB Output is correct
32 Correct 1811 ms 223228 KB Output is correct
33 Correct 1824 ms 223200 KB Output is correct
34 Correct 1471 ms 222880 KB Output is correct
35 Correct 1439 ms 222840 KB Output is correct
36 Correct 1469 ms 222628 KB Output is correct
37 Correct 1458 ms 222648 KB Output is correct
38 Correct 1441 ms 222868 KB Output is correct
39 Correct 1474 ms 221836 KB Output is correct
40 Correct 852 ms 155120 KB Output is correct
41 Correct 455 ms 64756 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37900 KB Output is correct
2 Correct 17 ms 37828 KB Output is correct
3 Correct 21 ms 37876 KB Output is correct
4 Correct 17 ms 37908 KB Output is correct
5 Correct 18 ms 37876 KB Output is correct
6 Correct 19 ms 38148 KB Output is correct
7 Correct 19 ms 38088 KB Output is correct
8 Correct 19 ms 38152 KB Output is correct
9 Correct 19 ms 37972 KB Output is correct
10 Correct 18 ms 37968 KB Output is correct
11 Correct 23 ms 38756 KB Output is correct
12 Correct 30 ms 41124 KB Output is correct
13 Correct 30 ms 41084 KB Output is correct
14 Correct 34 ms 41268 KB Output is correct
15 Correct 34 ms 41244 KB Output is correct
16 Correct 32 ms 41100 KB Output is correct
17 Correct 27 ms 40564 KB Output is correct
18 Correct 23 ms 38516 KB Output is correct
19 Runtime error 64 ms 80300 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -