oj.uz

Submission #1118888

# Submission time Handle Problem Language Result Execution time Memory
1118888 2024-11-26T10:44:19 Z Zflop Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 1785 ms 155980 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int NMAX = (int)1e6 + 50;
vector<vector<int>>R[NMAX];
int N,M,A[NMAX],ans[NMAX],mx[NMAX * 4];

void make(int i,int v,int l,int r,int x) {
	if (i == N + 1) return;
	if (l == r) {
		mx[x] = max(mx[x],v);
		return;
		}
	int mid = (l + r) / 2;
	if (i <= mid) make(i,v,l,mid,2 * x);
	else make(i,v,mid + 1,r,2 * x + 1);
	mx[x] = max(mx[2 * x],mx[2 * x + 1]);
	}

int get_maxim(int a,int b,int l,int r,int x) {
	if (a <= l && r <= b) 
		return mx[x];
	if (r < a || b < l)
		return 0;
	int mid = (l + r) / 2;
	return max(get_maxim(a,b,l,mid,2 * x),get_maxim(a,b,mid + 1,r,2 * x + 1));
	}

void solve() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N;++i)
		cin >> A[i];
	for (int i = 1; i <= M;++i) {
		int l,r,k; cin >> l >> r >> k;
		R[r].push_back({l,k,i});
		}
	A[N + 1] = (int)1e9 * 2;
	stack<int>q;
	q.push(N + 1);
	for (int i = 1; i <= N;++i) {
		while (A[i] >= A[q.top()])
			q.pop();
		make(q.top(),A[i] + A[q.top()],1,N,1);
		q.push(i);
		for (auto q : R[i]) {
			ans[q[2]] = get_maxim(q[0],i,1,N,1) <= q[1];
			}
		}
	for (int i = 1; i <= M;++i) {
		cout << ans[i] << '\n'; 
		//cout << i << ' ';
		}
	}


main() {
	solve();
	}

Compilation message

sortbooks.cpp:59:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   59 | main() {
      | ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23972 KB Output is correct
2 Correct 19 ms 25472 KB Output is correct
3 Correct 22 ms 25424 KB Output is correct
4 Correct 20 ms 25428 KB Output is correct
5 Correct 23 ms 25428 KB Output is correct
6 Correct 20 ms 23892 KB Output is correct
7 Correct 22 ms 23984 KB Output is correct
8 Correct 25 ms 23956 KB Output is correct
9 Correct 28 ms 23892 KB Output is correct
10 Correct 20 ms 23892 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23972 KB Output is correct
2 Correct 19 ms 25472 KB Output is correct
3 Correct 22 ms 25424 KB Output is correct
4 Correct 20 ms 25428 KB Output is correct
5 Correct 23 ms 25428 KB Output is correct
6 Correct 20 ms 23892 KB Output is correct
7 Correct 22 ms 23984 KB Output is correct
8 Correct 25 ms 23956 KB Output is correct
9 Correct 28 ms 23892 KB Output is correct
10 Correct 20 ms 23892 KB Output is correct
11 Correct 24 ms 24148 KB Output is correct
12 Correct 25 ms 24404 KB Output is correct
13 Correct 30 ms 24240 KB Output is correct
14 Correct 21 ms 24660 KB Output is correct
15 Correct 27 ms 24660 KB Output is correct
16 Correct 21 ms 24404 KB Output is correct
17 Correct 20 ms 24404 KB Output is correct
18 Correct 21 ms 24420 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1661 ms 121688 KB Output is correct
2 Correct 1572 ms 121736 KB Output is correct
3 Correct 1544 ms 121572 KB Output is correct
4 Correct 1468 ms 121664 KB Output is correct
5 Correct 1197 ms 109384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 35556 KB Output is correct
2 Correct 112 ms 37840 KB Output is correct
3 Correct 126 ms 33960 KB Output is correct
4 Correct 134 ms 34044 KB Output is correct
5 Correct 106 ms 34000 KB Output is correct
6 Correct 95 ms 33612 KB Output is correct
7 Correct 90 ms 33788 KB Output is correct
8 Correct 101 ms 33280 KB Output is correct
9 Correct 63 ms 32000 KB Output is correct
10 Correct 109 ms 33536 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23972 KB Output is correct
2 Correct 19 ms 25472 KB Output is correct
3 Correct 22 ms 25424 KB Output is correct
4 Correct 20 ms 25428 KB Output is correct
5 Correct 23 ms 25428 KB Output is correct
6 Correct 20 ms 23892 KB Output is correct
7 Correct 22 ms 23984 KB Output is correct
8 Correct 25 ms 23956 KB Output is correct
9 Correct 28 ms 23892 KB Output is correct
10 Correct 20 ms 23892 KB Output is correct
11 Correct 24 ms 24148 KB Output is correct
12 Correct 25 ms 24404 KB Output is correct
13 Correct 30 ms 24240 KB Output is correct
14 Correct 21 ms 24660 KB Output is correct
15 Correct 27 ms 24660 KB Output is correct
16 Correct 21 ms 24404 KB Output is correct
17 Correct 20 ms 24404 KB Output is correct
18 Correct 21 ms 24420 KB Output is correct
19 Correct 253 ms 52812 KB Output is correct
20 Correct 258 ms 52560 KB Output is correct
21 Correct 216 ms 52568 KB Output is correct
22 Correct 222 ms 52556 KB Output is correct
23 Correct 260 ms 52704 KB Output is correct
24 Correct 192 ms 48460 KB Output is correct
25 Correct 196 ms 46704 KB Output is correct
26 Correct 216 ms 46724 KB Output is correct
27 Correct 232 ms 46924 KB Output is correct
28 Correct 241 ms 46692 KB Output is correct
29 Correct 244 ms 46668 KB Output is correct
30 Correct 228 ms 46844 KB Output is correct
31 Correct 255 ms 46884 KB Output is correct
32 Correct 256 ms 46668 KB Output is correct
33 Correct 256 ms 48460 KB Output is correct
34 Correct 167 ms 46024 KB Output is correct
35 Correct 193 ms 45956 KB Output is correct
36 Correct 202 ms 45900 KB Output is correct
37 Correct 210 ms 45904 KB Output is correct
38 Correct 198 ms 45968 KB Output is correct
39 Correct 204 ms 47832 KB Output is correct
40 Correct 165 ms 44876 KB Output is correct
41 Correct 221 ms 44252 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23972 KB Output is correct
2 Correct 19 ms 25472 KB Output is correct
3 Correct 22 ms 25424 KB Output is correct
4 Correct 20 ms 25428 KB Output is correct
5 Correct 23 ms 25428 KB Output is correct
6 Correct 20 ms 23892 KB Output is correct
7 Correct 22 ms 23984 KB Output is correct
8 Correct 25 ms 23956 KB Output is correct
9 Correct 28 ms 23892 KB Output is correct
10 Correct 20 ms 23892 KB Output is correct
11 Correct 24 ms 24148 KB Output is correct
12 Correct 25 ms 24404 KB Output is correct
13 Correct 30 ms 24240 KB Output is correct
14 Correct 21 ms 24660 KB Output is correct
15 Correct 27 ms 24660 KB Output is correct
16 Correct 21 ms 24404 KB Output is correct
17 Correct 20 ms 24404 KB Output is correct
18 Correct 21 ms 24420 KB Output is correct
19 Correct 1661 ms 121688 KB Output is correct
20 Correct 1572 ms 121736 KB Output is correct
21 Correct 1544 ms 121572 KB Output is correct
22 Correct 1468 ms 121664 KB Output is correct
23 Correct 1197 ms 109384 KB Output is correct
24 Correct 138 ms 35556 KB Output is correct
25 Correct 112 ms 37840 KB Output is correct
26 Correct 126 ms 33960 KB Output is correct
27 Correct 134 ms 34044 KB Output is correct
28 Correct 106 ms 34000 KB Output is correct
29 Correct 95 ms 33612 KB Output is correct
30 Correct 90 ms 33788 KB Output is correct
31 Correct 101 ms 33280 KB Output is correct
32 Correct 63 ms 32000 KB Output is correct
33 Correct 109 ms 33536 KB Output is correct
34 Correct 253 ms 52812 KB Output is correct
35 Correct 258 ms 52560 KB Output is correct
36 Correct 216 ms 52568 KB Output is correct
37 Correct 222 ms 52556 KB Output is correct
38 Correct 260 ms 52704 KB Output is correct
39 Correct 192 ms 48460 KB Output is correct
40 Correct 196 ms 46704 KB Output is correct
41 Correct 216 ms 46724 KB Output is correct
42 Correct 232 ms 46924 KB Output is correct
43 Correct 241 ms 46692 KB Output is correct
44 Correct 244 ms 46668 KB Output is correct
45 Correct 228 ms 46844 KB Output is correct
46 Correct 255 ms 46884 KB Output is correct
47 Correct 256 ms 46668 KB Output is correct
48 Correct 256 ms 48460 KB Output is correct
49 Correct 167 ms 46024 KB Output is correct
50 Correct 193 ms 45956 KB Output is correct
51 Correct 202 ms 45900 KB Output is correct
52 Correct 210 ms 45904 KB Output is correct
53 Correct 198 ms 45968 KB Output is correct
54 Correct 204 ms 47832 KB Output is correct
55 Correct 165 ms 44876 KB Output is correct
56 Correct 221 ms 44252 KB Output is correct
57 Correct 1658 ms 155412 KB Output is correct
58 Correct 1785 ms 155332 KB Output is correct
59 Correct 1356 ms 155828 KB Output is correct
60 Correct 1427 ms 155792 KB Output is correct
61 Correct 1488 ms 155880 KB Output is correct
62 Correct 1571 ms 155980 KB Output is correct
63 Correct 1105 ms 137664 KB Output is correct
64 Correct 1012 ms 137612 KB Output is correct
65 Correct 1315 ms 139448 KB Output is correct
66 Correct 1324 ms 139568 KB Output is correct
67 Correct 1322 ms 139596 KB Output is correct
68 Correct 1354 ms 139184 KB Output is correct
69 Correct 1288 ms 139212 KB Output is correct
70 Correct 1241 ms 139160 KB Output is correct
71 Correct 1396 ms 139104 KB Output is correct
72 Correct 1355 ms 139076 KB Output is correct
73 Correct 931 ms 131148 KB Output is correct
74 Correct 1002 ms 131860 KB Output is correct
75 Correct 932 ms 131148 KB Output is correct
76 Correct 1053 ms 131116 KB Output is correct
77 Correct 976 ms 130756 KB Output is correct
78 Correct 1249 ms 135888 KB Output is correct
79 Correct 866 ms 119456 KB Output is correct
80 Correct 1263 ms 126936 KB Output is correct