oj.uz

Submission #1096198

# Submission time Handle Problem Language Result Execution time Memory
1096198 2024-10-04T05:27:26 Z stdfloat Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 2819 ms 262148 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define sz(v)  (int)(v).size()
#define all(v) (v).begin(), v.end()

int mx;

vector<int> a, st, vis;

vector<vector<int>> v;

void bld(int nd, int l, int r) {
	if (l == r) {
		vis[nd] = 0; st[nd] = a[l]; v[nd] = {a[l]};
		return;
	}

	int ch = (nd << 1) + 1, md = l + r >> 1;
	bld(ch, l, md); bld(ch + 1, md + 1, r);

	st[nd] = max(st[ch], st[ch + 1]);

	v[nd].assign(sz(v[ch]) + sz(v[ch + 1]), 0);
	merge(all(v[ch]), all(v[ch + 1]), v[nd].begin());
	
	int mx = 0;
	for (int i = l; i <= r; i++) {
		if (mx > a[i]) vis[nd] = max(vis[nd], mx + a[i]);
		else mx = a[i];
	}
}

bool fnd(int nd, int l, int r, int x, int y, int k) {
	if (r < x || y < l) return true;

	if (x <= l && r <= y) {
		bool tr = (vis[nd] <= k && (mx <= v[nd][0] || mx + *--lower_bound(all(v[nd]), mx) <= k));
		mx = max(mx, st[nd]);
		return tr;
	}

	int ch = (nd << 1) + 1, md = l + r >> 1;
	return (!fnd(ch, l, md, x, y, k) || !fnd(ch + 1, md + 1, r, x, y, k) ? false : true);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n, q;
	cin >> n >> q;

	a.assign(n, 0);
	for (auto &i : a)
		cin >> i;

	v.assign(n << 2, {});
	st = vis = vector<int>(n << 2);
	bld(0, 0, n - 1);

	while (q--) {
		int l, r, k;
		cin >> l >> r >> k; l--; r--;

		mx = 0;
		cout << fnd(0, 0, n - 1, l, r, k) << endl;
	}
}

Compilation message

sortbooks.cpp: In function 'void bld(int, int, int)':
sortbooks.cpp:21:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |  int ch = (nd << 1) + 1, md = l + r >> 1;
      |                               ~~^~~
sortbooks.cpp: In function 'bool fnd(int, int, int, int, int, int)':
sortbooks.cpp:45:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |  int ch = (nd << 1) + 1, md = l + r >> 1;
      |                               ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 7 ms 604 KB Output is correct
12 Correct 5 ms 1572 KB Output is correct
13 Correct 6 ms 1372 KB Output is correct
14 Correct 9 ms 1564 KB Output is correct
15 Correct 9 ms 1368 KB Output is correct
16 Correct 8 ms 1372 KB Output is correct
17 Correct 8 ms 1372 KB Output is correct
18 Correct 7 ms 1608 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2084 ms 262144 KB Output is correct
2 Correct 2088 ms 262144 KB Output is correct
3 Correct 2113 ms 262144 KB Output is correct
4 Correct 2032 ms 262144 KB Output is correct
5 Runtime error 2819 ms 262148 KB Memory limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 26708 KB Output is correct
2 Correct 188 ms 26600 KB Output is correct
3 Correct 198 ms 26704 KB Output is correct
4 Correct 208 ms 26704 KB Output is correct
5 Correct 199 ms 26708 KB Output is correct
6 Correct 156 ms 26568 KB Output is correct
7 Correct 160 ms 26448 KB Output is correct
8 Correct 178 ms 26708 KB Output is correct
9 Correct 121 ms 1880 KB Output is correct
10 Correct 179 ms 26660 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 7 ms 604 KB Output is correct
12 Correct 5 ms 1572 KB Output is correct
13 Correct 6 ms 1372 KB Output is correct
14 Correct 9 ms 1564 KB Output is correct
15 Correct 9 ms 1368 KB Output is correct
16 Correct 8 ms 1372 KB Output is correct
17 Correct 8 ms 1372 KB Output is correct
18 Correct 7 ms 1608 KB Output is correct
19 Correct 445 ms 56972 KB Output is correct
20 Correct 490 ms 56916 KB Output is correct
21 Correct 404 ms 56660 KB Output is correct
22 Correct 384 ms 56792 KB Output is correct
23 Correct 405 ms 56756 KB Output is correct
24 Correct 374 ms 56660 KB Output is correct
25 Correct 384 ms 56648 KB Output is correct
26 Correct 447 ms 56764 KB Output is correct
27 Correct 395 ms 56912 KB Output is correct
28 Correct 428 ms 56912 KB Output is correct
29 Correct 392 ms 56912 KB Output is correct
30 Correct 411 ms 56908 KB Output is correct
31 Correct 395 ms 56964 KB Output is correct
32 Correct 410 ms 56852 KB Output is correct
33 Correct 418 ms 56916 KB Output is correct
34 Correct 336 ms 56532 KB Output is correct
35 Correct 409 ms 56656 KB Output is correct
36 Correct 342 ms 56404 KB Output is correct
37 Correct 349 ms 56400 KB Output is correct
38 Correct 358 ms 56404 KB Output is correct
39 Correct 387 ms 55376 KB Output is correct
40 Correct 361 ms 37472 KB Output is correct
41 Correct 403 ms 55124 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 7 ms 604 KB Output is correct
12 Correct 5 ms 1572 KB Output is correct
13 Correct 6 ms 1372 KB Output is correct
14 Correct 9 ms 1564 KB Output is correct
15 Correct 9 ms 1368 KB Output is correct
16 Correct 8 ms 1372 KB Output is correct
17 Correct 8 ms 1372 KB Output is correct
18 Correct 7 ms 1608 KB Output is correct
19 Correct 2084 ms 262144 KB Output is correct
20 Correct 2088 ms 262144 KB Output is correct
21 Correct 2113 ms 262144 KB Output is correct
22 Correct 2032 ms 262144 KB Output is correct
23 Runtime error 2819 ms 262148 KB Memory limit exceeded
24 Halted 0 ms 0 KB -