Submission #1094708

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1094708	2024-09-30T10:25:41 Z	stdfloat	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	77 / 100	3000 ms	43860 KB

sortbooks

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

using ll = long long;

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

#define ff  first
#define ss  second
#define pii pair<int, int>

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

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

	vector<int> a(n);
	for (auto &i : a)
		cin >> i;

	int sz = sqrt(n);
	while (sz * sz < n) sz++;
	while (sz * sz > n) sz--;

	vector<int> b = a, v((n - 1) / sz + 1);
	for (int i = 0; i < sz(v); i++) {
		int mx = 0;
		for (int j = i * sz; j < min(n, (i + 1) * sz); j++) {
			if (a[j] < mx) v[i] = max(v[i], a[j] + mx);
			mx = max(mx, a[j]);
		}

		// cout << i << ' ' << v[i] << ' ' << i * sz << ' ' << min(n, (i + 1) * sz) - 1 << '\n';

		sort(b.begin() + i * sz, b.begin() + min(n, (i + 1) * sz));
	}

	// cout << "sz " << sz << endl;

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

		if (l / sz == r / sz) {
			int mx = 0;
			bool tr = true;
			for (int i = l; i <= r && tr; i++) {
				tr = (a[i] >= mx || a[i] + mx <= k);
				mx = max(mx, a[i]);
			}
 
 			cout << tr << '\n';
 			continue;
		}

		int mx = 0;
		bool tr = true;
		for (int i = l; i < (l / sz + 1) * sz && tr; i++) {
			tr = (a[i] >= mx || a[i] + mx <= k);
			mx = max(mx, a[i]);
		}

		// cout << tr << ' ' << l << ' ' << (l / sz + 1) * sz << endl;

		if (!tr) {
			cout << "0\n";
			continue;
		}

		for (int i = l / sz + 1; i < r / sz && tr; i++) {
			int x = i * sz, y = (i + 1) * sz - 1;
			tr = (max(v[i], (mx > b[x] ? mx + *--lower_bound(b.begin() + x, b.begin() + y + 1, mx) : 0)) <= k);
			mx = max(mx, b[y]);
		}

		int x = r / sz * sz;
		for (int i = x; i <= r && tr; i++) {
			tr = (a[i] >= mx || a[i] + mx <= k);
			mx = max(mx, a[i]);
		}

		// cout << x << ' ' << mx << ' ' << mx2 << ' ' << tr << endl;

		cout << tr << '\n';
	}
}

Subtask #1
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 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	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 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	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	2 ms	604 KB	Output is correct
13	Correct	1 ms	604 KB	Output is correct
14	Correct	2 ms	588 KB	Output is correct
15	Correct	2 ms	604 KB	Output is correct
16	Correct	2 ms	604 KB	Output is correct
17	Correct	3 ms	348 KB	Output is correct
18	Correct	2 ms	344 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	339 ms	42068 KB	Output is correct
2	Correct	342 ms	43092 KB	Output is correct
3	Correct	354 ms	42832 KB	Output is correct
4	Correct	307 ms	43092 KB	Output is correct
5	Correct	1725 ms	43028 KB	Output is correct

Subtask #4
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	50 ms	3404 KB	Output is correct
2	Correct	87 ms	3332 KB	Output is correct
3	Correct	72 ms	3372 KB	Output is correct
4	Correct	71 ms	3268 KB	Output is correct
5	Correct	65 ms	3412 KB	Output is correct
6	Correct	59 ms	3152 KB	Output is correct
7	Correct	65 ms	3156 KB	Output is correct
8	Correct	89 ms	2896 KB	Output is correct
9	Correct	23 ms	1884 KB	Output is correct
10	Correct	93 ms	2924 KB	Output is correct

Subtask #5
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 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	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	2 ms	604 KB	Output is correct
13	Correct	1 ms	604 KB	Output is correct
14	Correct	2 ms	588 KB	Output is correct
15	Correct	2 ms	604 KB	Output is correct
16	Correct	2 ms	604 KB	Output is correct
17	Correct	3 ms	348 KB	Output is correct
18	Correct	2 ms	344 KB	Output is correct
19	Correct	128 ms	8892 KB	Output is correct
20	Correct	126 ms	8784 KB	Output is correct
21	Correct	219 ms	8788 KB	Output is correct
22	Correct	232 ms	8784 KB	Output is correct
23	Correct	213 ms	8696 KB	Output is correct
24	Correct	221 ms	8528 KB	Output is correct
25	Correct	262 ms	8532 KB	Output is correct
26	Correct	227 ms	8664 KB	Output is correct
27	Correct	226 ms	8812 KB	Output is correct
28	Correct	217 ms	8764 KB	Output is correct
29	Correct	169 ms	8760 KB	Output is correct
30	Correct	173 ms	8912 KB	Output is correct
31	Correct	175 ms	8784 KB	Output is correct
32	Correct	179 ms	8788 KB	Output is correct
33	Correct	185 ms	9108 KB	Output is correct
34	Correct	187 ms	8528 KB	Output is correct
35	Correct	187 ms	8444 KB	Output is correct
36	Correct	198 ms	8276 KB	Output is correct
37	Correct	189 ms	8272 KB	Output is correct
38	Correct	195 ms	8528 KB	Output is correct
39	Correct	238 ms	7504 KB	Output is correct
40	Correct	230 ms	6228 KB	Output is correct
41	Correct	234 ms	6880 KB	Output is correct

Subtask #6
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 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	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	2 ms	604 KB	Output is correct
13	Correct	1 ms	604 KB	Output is correct
14	Correct	2 ms	588 KB	Output is correct
15	Correct	2 ms	604 KB	Output is correct
16	Correct	2 ms	604 KB	Output is correct
17	Correct	3 ms	348 KB	Output is correct
18	Correct	2 ms	344 KB	Output is correct
19	Correct	339 ms	42068 KB	Output is correct
20	Correct	342 ms	43092 KB	Output is correct
21	Correct	354 ms	42832 KB	Output is correct
22	Correct	307 ms	43092 KB	Output is correct
23	Correct	1725 ms	43028 KB	Output is correct
24	Correct	50 ms	3404 KB	Output is correct
25	Correct	87 ms	3332 KB	Output is correct
26	Correct	72 ms	3372 KB	Output is correct
27	Correct	71 ms	3268 KB	Output is correct
28	Correct	65 ms	3412 KB	Output is correct
29	Correct	59 ms	3152 KB	Output is correct
30	Correct	65 ms	3156 KB	Output is correct
31	Correct	89 ms	2896 KB	Output is correct
32	Correct	23 ms	1884 KB	Output is correct
33	Correct	93 ms	2924 KB	Output is correct
34	Correct	128 ms	8892 KB	Output is correct
35	Correct	126 ms	8784 KB	Output is correct
36	Correct	219 ms	8788 KB	Output is correct
37	Correct	232 ms	8784 KB	Output is correct
38	Correct	213 ms	8696 KB	Output is correct
39	Correct	221 ms	8528 KB	Output is correct
40	Correct	262 ms	8532 KB	Output is correct
41	Correct	227 ms	8664 KB	Output is correct
42	Correct	226 ms	8812 KB	Output is correct
43	Correct	217 ms	8764 KB	Output is correct
44	Correct	169 ms	8760 KB	Output is correct
45	Correct	173 ms	8912 KB	Output is correct
46	Correct	175 ms	8784 KB	Output is correct
47	Correct	179 ms	8788 KB	Output is correct
48	Correct	185 ms	9108 KB	Output is correct
49	Correct	187 ms	8528 KB	Output is correct
50	Correct	187 ms	8444 KB	Output is correct
51	Correct	198 ms	8276 KB	Output is correct
52	Correct	189 ms	8272 KB	Output is correct
53	Correct	195 ms	8528 KB	Output is correct
54	Correct	238 ms	7504 KB	Output is correct
55	Correct	230 ms	6228 KB	Output is correct
56	Correct	234 ms	6880 KB	Output is correct
57	Correct	1038 ms	43744 KB	Output is correct
58	Correct	1121 ms	43752 KB	Output is correct
59	Correct	1921 ms	43668 KB	Output is correct
60	Correct	1819 ms	43660 KB	Output is correct
61	Correct	1868 ms	43600 KB	Output is correct
62	Correct	1897 ms	43568 KB	Output is correct
63	Correct	2540 ms	41864 KB	Output is correct
64	Correct	2626 ms	41768 KB	Output is correct
65	Correct	2077 ms	43524 KB	Output is correct
66	Correct	2104 ms	43604 KB	Output is correct
67	Correct	2077 ms	43332 KB	Output is correct
68	Correct	1572 ms	43708 KB	Output is correct
69	Correct	1685 ms	43748 KB	Output is correct
70	Correct	1664 ms	43860 KB	Output is correct
71	Correct	1672 ms	43760 KB	Output is correct
72	Correct	1743 ms	43776 KB	Output is correct
73	Correct	1962 ms	40204 KB	Output is correct
74	Correct	2008 ms	41312 KB	Output is correct
75	Correct	1962 ms	40400 KB	Output is correct
76	Correct	1888 ms	40276 KB	Output is correct
77	Correct	2001 ms	40280 KB	Output is correct
78	Correct	2493 ms	37720 KB	Output is correct
79	Correct	2072 ms	29008 KB	Output is correct
80	Execution timed out	3017 ms	34900 KB	Time limit exceeded
81	Halted	0 ms	0 KB	-

Submission #1094708

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 9.0 / 9.0

Subtask #3 13.0 / 13.0

Subtask #4 17.0 / 17.0

Subtask #5 30.0 / 30.0

Subtask #6 0 / 23.0

Subtask #1
8.0 / 8.0

Subtask #2
9.0 / 9.0

Subtask #3
13.0 / 13.0

Subtask #4
17.0 / 17.0

Subtask #5
30.0 / 30.0

Subtask #6
0 / 23.0