oj.uz

Submission #887285

# Submission time Handle Problem Language Result Execution time Memory
887285 2023-12-14T07:46:54 Z alex_2008 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 2059 ms 116768 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#include <bitset>
typedef long long ll;
using namespace std;
const int N = 1e6 + 10;
struct query {
	int l;
	int r;
	int k;
	int ind;
};
bool cmp(query x, query y) {
	return x.l > y.l;
}
int a[N], l[N];
int b[N];
int tree[4 * N];
int ans[N];
void update(int v, int tl, int tr, int pos, int val) {
	if (tl == tr) {
		tree[v] = val;
		return;
	}
	int tm = (tl + tr) / 2;
	if (pos <= tm) {
		update(2 * v, tl, tm, pos, val);
	}
	else {
		update(2 * v + 1, tm + 1, tr, pos, val);
	}
	tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}
int MAX(int v, int tl, int tr, int l, int r) {
	if (tr < l || tl > r) return 0;
	if (tl >= l && tr <= r) return tree[v];
	int tm = (tl + tr) / 2;
	return max(MAX(2 * v, tl, tm, l, r),
		MAX(2 * v + 1, tm + 1, tr, l, r));
}
int main() {
	int n, q;
	cin >> n >> q;
	a[0] = 1e9 + 10;
	vector <vector<int>> updates(n);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		l[i] = i - 1;
		while (a[i] >= a[l[i]]) {
			l[i] = l[l[i]];
		}
		b[i] = a[i] + a[l[i]];
		updates[l[i]].push_back(i);
	}
	vector <query> v;
	for (int i = 1; i <= q; i++) {
		int l, r, k;
		cin >> l >> r >> k;
		v.push_back({ l, r, k, i });
	}
	sort(v.begin(), v.end(), cmp);
	int prev_ind = n - 1;
	for (auto it : v) {
		int l = it.l, r = it.r, k = it.k, ind = it.ind;
		while (prev_ind >= l) {
			for (auto it : updates[prev_ind]) {
				update(1, 1, n, it, b[it]);
			}
			prev_ind--;
		}
		ans[ind] = (k >= MAX(1, 1, n, l, r))? 1: 0;
	}
	for (int i = 1; i <= q; i++) {
		cout << ans[i] << "\n";
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8792 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 1 ms 6628 KB Output is correct
9 Correct 1 ms 6744 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8792 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 1 ms 6628 KB Output is correct
9 Correct 1 ms 6744 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 4 ms 8792 KB Output is correct
12 Correct 6 ms 8956 KB Output is correct
13 Correct 6 ms 8796 KB Output is correct
14 Correct 8 ms 9008 KB Output is correct
15 Correct 8 ms 9088 KB Output is correct
16 Correct 7 ms 7004 KB Output is correct
17 Correct 6 ms 6748 KB Output is correct
18 Correct 7 ms 7004 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1621 ms 115220 KB Output is correct
2 Correct 2059 ms 116176 KB Output is correct
3 Correct 1639 ms 115652 KB Output is correct
4 Correct 1649 ms 115896 KB Output is correct
5 Correct 1465 ms 95512 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 17344 KB Output is correct
2 Correct 122 ms 18712 KB Output is correct
3 Correct 115 ms 13380 KB Output is correct
4 Correct 111 ms 13276 KB Output is correct
5 Correct 109 ms 13384 KB Output is correct
6 Correct 101 ms 17456 KB Output is correct
7 Correct 103 ms 17456 KB Output is correct
8 Correct 101 ms 14276 KB Output is correct
9 Correct 66 ms 10688 KB Output is correct
10 Correct 99 ms 14064 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8792 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 1 ms 6628 KB Output is correct
9 Correct 1 ms 6744 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 4 ms 8792 KB Output is correct
12 Correct 6 ms 8956 KB Output is correct
13 Correct 6 ms 8796 KB Output is correct
14 Correct 8 ms 9008 KB Output is correct
15 Correct 8 ms 9088 KB Output is correct
16 Correct 7 ms 7004 KB Output is correct
17 Correct 6 ms 6748 KB Output is correct
18 Correct 7 ms 7004 KB Output is correct
19 Correct 332 ms 23944 KB Output is correct
20 Correct 308 ms 23996 KB Output is correct
21 Correct 307 ms 24516 KB Output is correct
22 Correct 295 ms 25228 KB Output is correct
23 Correct 297 ms 24436 KB Output is correct
24 Correct 263 ms 18756 KB Output is correct
25 Correct 267 ms 17880 KB Output is correct
26 Correct 278 ms 18692 KB Output is correct
27 Correct 273 ms 17824 KB Output is correct
28 Correct 284 ms 18112 KB Output is correct
29 Correct 276 ms 17972 KB Output is correct
30 Correct 283 ms 18932 KB Output is correct
31 Correct 276 ms 18496 KB Output is correct
32 Correct 279 ms 17728 KB Output is correct
33 Correct 280 ms 17824 KB Output is correct
34 Correct 259 ms 22064 KB Output is correct
35 Correct 260 ms 22020 KB Output is correct
36 Correct 254 ms 22332 KB Output is correct
37 Correct 249 ms 21936 KB Output is correct
38 Correct 276 ms 22136 KB Output is correct
39 Correct 242 ms 19380 KB Output is correct
40 Correct 197 ms 16568 KB Output is correct
41 Correct 229 ms 19528 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8792 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 1 ms 6628 KB Output is correct
9 Correct 1 ms 6744 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 4 ms 8792 KB Output is correct
12 Correct 6 ms 8956 KB Output is correct
13 Correct 6 ms 8796 KB Output is correct
14 Correct 8 ms 9008 KB Output is correct
15 Correct 8 ms 9088 KB Output is correct
16 Correct 7 ms 7004 KB Output is correct
17 Correct 6 ms 6748 KB Output is correct
18 Correct 7 ms 7004 KB Output is correct
19 Correct 1621 ms 115220 KB Output is correct
20 Correct 2059 ms 116176 KB Output is correct
21 Correct 1639 ms 115652 KB Output is correct
22 Correct 1649 ms 115896 KB Output is correct
23 Correct 1465 ms 95512 KB Output is correct
24 Correct 124 ms 17344 KB Output is correct
25 Correct 122 ms 18712 KB Output is correct
26 Correct 115 ms 13380 KB Output is correct
27 Correct 111 ms 13276 KB Output is correct
28 Correct 109 ms 13384 KB Output is correct
29 Correct 101 ms 17456 KB Output is correct
30 Correct 103 ms 17456 KB Output is correct
31 Correct 101 ms 14276 KB Output is correct
32 Correct 66 ms 10688 KB Output is correct
33 Correct 99 ms 14064 KB Output is correct
34 Correct 332 ms 23944 KB Output is correct
35 Correct 308 ms 23996 KB Output is correct
36 Correct 307 ms 24516 KB Output is correct
37 Correct 295 ms 25228 KB Output is correct
38 Correct 297 ms 24436 KB Output is correct
39 Correct 263 ms 18756 KB Output is correct
40 Correct 267 ms 17880 KB Output is correct
41 Correct 278 ms 18692 KB Output is correct
42 Correct 273 ms 17824 KB Output is correct
43 Correct 284 ms 18112 KB Output is correct
44 Correct 276 ms 17972 KB Output is correct
45 Correct 283 ms 18932 KB Output is correct
46 Correct 276 ms 18496 KB Output is correct
47 Correct 279 ms 17728 KB Output is correct
48 Correct 280 ms 17824 KB Output is correct
49 Correct 259 ms 22064 KB Output is correct
50 Correct 260 ms 22020 KB Output is correct
51 Correct 254 ms 22332 KB Output is correct
52 Correct 249 ms 21936 KB Output is correct
53 Correct 276 ms 22136 KB Output is correct
54 Correct 242 ms 19380 KB Output is correct
55 Correct 197 ms 16568 KB Output is correct
56 Correct 229 ms 19528 KB Output is correct
57 Correct 1683 ms 116768 KB Output is correct
58 Correct 1691 ms 116076 KB Output is correct
59 Correct 1633 ms 116724 KB Output is correct
60 Correct 1626 ms 116472 KB Output is correct
61 Correct 1616 ms 116500 KB Output is correct
62 Correct 1670 ms 116608 KB Output is correct
63 Correct 1344 ms 94528 KB Output is correct
64 Correct 1345 ms 93716 KB Output is correct
65 Correct 1440 ms 95552 KB Output is correct
66 Correct 1454 ms 96188 KB Output is correct
67 Correct 1469 ms 95712 KB Output is correct
68 Correct 1459 ms 96564 KB Output is correct
69 Correct 1462 ms 96492 KB Output is correct
70 Correct 1454 ms 96572 KB Output is correct
71 Correct 1455 ms 95788 KB Output is correct
72 Correct 1463 ms 95672 KB Output is correct
73 Correct 1358 ms 98596 KB Output is correct
74 Correct 1353 ms 99788 KB Output is correct
75 Correct 1319 ms 98732 KB Output is correct
76 Correct 1296 ms 99084 KB Output is correct
77 Correct 1299 ms 98764 KB Output is correct
78 Correct 1304 ms 98472 KB Output is correct
79 Correct 1014 ms 74468 KB Output is correct
80 Correct 1256 ms 94752 KB Output is correct