oj.uz

답안 #1096202

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1096202 2024-10-04T05:32:36 Z stdfloat Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
77 / 100
 2741 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) {
		if (vis[nd] > k || (mx > v[nd][0] && mx + *--lower_bound(all(v[nd]), mx) > k)) return false;

		mx = max(mx, st[nd]);
		return true;
	}

	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:46:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |  int ch = (nd << 1) + 1, md = l + r >> 1;
      |                               ~~^~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 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 348 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

# 결과 실행 시간 메모리 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 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 5 ms 856 KB Output is correct
12 Correct 5 ms 1880 KB Output is correct
13 Correct 6 ms 1628 KB Output is correct
14 Correct 8 ms 1756 KB Output is correct
15 Correct 8 ms 1760 KB Output is correct
16 Correct 8 ms 1676 KB Output is correct
17 Correct 8 ms 1496 KB Output is correct
18 Correct 8 ms 1628 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1968 ms 262144 KB Output is correct
2 Correct 2001 ms 262144 KB Output is correct
3 Correct 1940 ms 262144 KB Output is correct
4 Correct 1895 ms 262144 KB Output is correct
5 Correct 2741 ms 262144 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 200 ms 26840 KB Output is correct
2 Correct 170 ms 26776 KB Output is correct
3 Correct 182 ms 26708 KB Output is correct
4 Correct 191 ms 26708 KB Output is correct
5 Correct 187 ms 26808 KB Output is correct
6 Correct 152 ms 26704 KB Output is correct
7 Correct 160 ms 26816 KB Output is correct
8 Correct 179 ms 26448 KB Output is correct
9 Correct 120 ms 1872 KB Output is correct
10 Correct 162 ms 26392 KB Output is correct

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 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 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 5 ms 856 KB Output is correct
12 Correct 5 ms 1880 KB Output is correct
13 Correct 6 ms 1628 KB Output is correct
14 Correct 8 ms 1756 KB Output is correct
15 Correct 8 ms 1760 KB Output is correct
16 Correct 8 ms 1676 KB Output is correct
17 Correct 8 ms 1496 KB Output is correct
18 Correct 8 ms 1628 KB Output is correct
19 Correct 406 ms 55892 KB Output is correct
20 Correct 432 ms 55892 KB Output is correct
21 Correct 400 ms 55636 KB Output is correct
22 Correct 392 ms 55648 KB Output is correct
23 Correct 405 ms 55892 KB Output is correct
24 Correct 398 ms 56652 KB Output is correct
25 Correct 430 ms 56776 KB Output is correct
26 Correct 422 ms 56660 KB Output is correct
27 Correct 432 ms 56912 KB Output is correct
28 Correct 453 ms 56912 KB Output is correct
29 Correct 443 ms 56776 KB Output is correct
30 Correct 413 ms 56912 KB Output is correct
31 Correct 412 ms 55888 KB Output is correct
32 Correct 407 ms 55888 KB Output is correct
33 Correct 401 ms 56284 KB Output is correct
34 Correct 330 ms 55632 KB Output is correct
35 Correct 333 ms 55792 KB Output is correct
36 Correct 342 ms 55376 KB Output is correct
37 Correct 357 ms 55376 KB Output is correct
38 Correct 343 ms 55636 KB Output is correct
39 Correct 401 ms 55128 KB Output is correct
40 Correct 347 ms 37204 KB Output is correct
41 Correct 399 ms 55116 KB Output is correct

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 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 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 5 ms 856 KB Output is correct
12 Correct 5 ms 1880 KB Output is correct
13 Correct 6 ms 1628 KB Output is correct
14 Correct 8 ms 1756 KB Output is correct
15 Correct 8 ms 1760 KB Output is correct
16 Correct 8 ms 1676 KB Output is correct
17 Correct 8 ms 1496 KB Output is correct
18 Correct 8 ms 1628 KB Output is correct
19 Correct 1968 ms 262144 KB Output is correct
20 Correct 2001 ms 262144 KB Output is correct
21 Correct 1940 ms 262144 KB Output is correct
22 Correct 1895 ms 262144 KB Output is correct
23 Correct 2741 ms 262144 KB Output is correct
24 Correct 200 ms 26840 KB Output is correct
25 Correct 170 ms 26776 KB Output is correct
26 Correct 182 ms 26708 KB Output is correct
27 Correct 191 ms 26708 KB Output is correct
28 Correct 187 ms 26808 KB Output is correct
29 Correct 152 ms 26704 KB Output is correct
30 Correct 160 ms 26816 KB Output is correct
31 Correct 179 ms 26448 KB Output is correct
32 Correct 120 ms 1872 KB Output is correct
33 Correct 162 ms 26392 KB Output is correct
34 Correct 406 ms 55892 KB Output is correct
35 Correct 432 ms 55892 KB Output is correct
36 Correct 400 ms 55636 KB Output is correct
37 Correct 392 ms 55648 KB Output is correct
38 Correct 405 ms 55892 KB Output is correct
39 Correct 398 ms 56652 KB Output is correct
40 Correct 430 ms 56776 KB Output is correct
41 Correct 422 ms 56660 KB Output is correct
42 Correct 432 ms 56912 KB Output is correct
43 Correct 453 ms 56912 KB Output is correct
44 Correct 443 ms 56776 KB Output is correct
45 Correct 413 ms 56912 KB Output is correct
46 Correct 412 ms 55888 KB Output is correct
47 Correct 407 ms 55888 KB Output is correct
48 Correct 401 ms 56284 KB Output is correct
49 Correct 330 ms 55632 KB Output is correct
50 Correct 333 ms 55792 KB Output is correct
51 Correct 342 ms 55376 KB Output is correct
52 Correct 357 ms 55376 KB Output is correct
53 Correct 343 ms 55636 KB Output is correct
54 Correct 401 ms 55128 KB Output is correct
55 Correct 347 ms 37204 KB Output is correct
56 Correct 399 ms 55116 KB Output is correct
57 Correct 2279 ms 262144 KB Output is correct
58 Correct 2201 ms 262144 KB Output is correct
59 Correct 2451 ms 262144 KB Output is correct
60 Correct 2175 ms 262144 KB Output is correct
61 Correct 2290 ms 262144 KB Output is correct
62 Correct 2420 ms 262144 KB Output is correct
63 Correct 1862 ms 262144 KB Output is correct
64 Correct 1829 ms 262144 KB Output is correct
65 Correct 2613 ms 262144 KB Output is correct
66 Correct 2550 ms 262144 KB Output is correct
67 Correct 2354 ms 262144 KB Output is correct
68 Runtime error 2698 ms 262148 KB Memory limit exceeded
69 Halted 0 ms 0 KB -