oj.uz

Submission #887281

# Submission time Handle Problem Language Result Execution time Memory
887281 2023-12-14T07:35:29 Z alex_2008 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 658 ms 262144 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;
int sz = 0;
struct Node {
	int left;
	int right;
	int mx;
};
int a[N], l[N];
int b[N];
int root[N];
Node tree[21 * N];
void build_tree(int v, int tl, int tr) {
	tree[v].left = 0;
	tree[v].right = 0;
	tree[v].mx = 0;
	if (tl != tr) {
		tree[v].left = ++sz;
		tree[v].right = ++sz;
		int tm = (tl + tr) / 2;
		build_tree(tree[v].left, tl, tm);
		build_tree(tree[v].right, tm + 1, tr);
	}
}
void update(int v, int prev_v, int tl, int tr, int pos, int val) {
	if (tl == tr) {
		tree[v].mx = val;
		return;
	}
	int tm = (tl + tr) / 2;
	if (pos <= tm) {
		tree[v].right = tree[prev_v].right;
		tree[v].left = ++sz;
		update(tree[v].left, tree[prev_v].left, tl, tm, pos, val);
	}
	else {
		tree[v].left = tree[prev_v].left;
		tree[v].right = ++sz;
		update(tree[v].right, tree[prev_v].right, tm + 1, tr, pos, val);
	}
	tree[v].mx = max(tree[tree[v].left].mx, tree[tree[v].right].mx);
}
int MAX(int v, int tl, int tr, int l, int r) {
	if (tl > r || tr < l) return 0;
	if (tl >= l && tr <= r) return tree[v].mx;
	int tm = (tl + tr) / 2;
	return max(MAX(tree[v].left, tl, tm, l, r), MAX(tree[v].right, tm + 1, tr, l, r));
}
int main() {
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= 21 * n; i++) {
		tree[i] = { 0, 0, 0 };
	}
	a[0] = 1e9 + 10;
	vector <pair<int, int>> updates;
	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.push_back({ l[i], i });
	}
	updates.push_back({ n, 0 });
	sort(updates.begin(), updates.end());
	root[n] = ++sz;
	build_tree(root[n], 1, n);
	for (int i = n - 1; i >= 0; i--) {
		root[i] = ++sz;
		update(root[i], root[i + 1], 1, n, updates[i].second, b[updates[i].second]);
	}
	while (q--) {
		int l, r, k;
		cin >> l >> r >> k;
		int ind = lower_bound(updates.begin(), updates.end(), make_pair(l, 0)) - updates.begin();
		if (MAX(root[ind], 1, n, l, r) <= k) cout << 1 << "\n";
		else cout << 0 << "\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 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 2 ms 8792 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8540 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 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 2 ms 8792 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 8 ms 10844 KB Output is correct
12 Correct 9 ms 10844 KB Output is correct
13 Correct 10 ms 10988 KB Output is correct
14 Correct 14 ms 10844 KB Output is correct
15 Correct 14 ms 11000 KB Output is correct
16 Correct 13 ms 10844 KB Output is correct
17 Correct 12 ms 10844 KB Output is correct
18 Correct 12 ms 11004 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 354 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 38600 KB Output is correct
2 Correct 258 ms 38776 KB Output is correct
3 Correct 258 ms 38596 KB Output is correct
4 Correct 240 ms 38596 KB Output is correct
5 Correct 239 ms 38580 KB Output is correct
6 Correct 234 ms 38636 KB Output is correct
7 Correct 241 ms 38732 KB Output is correct
8 Correct 227 ms 38596 KB Output is correct
9 Correct 180 ms 8796 KB Output is correct
10 Correct 231 ms 38652 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 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 2 ms 8792 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 8 ms 10844 KB Output is correct
12 Correct 9 ms 10844 KB Output is correct
13 Correct 10 ms 10988 KB Output is correct
14 Correct 14 ms 10844 KB Output is correct
15 Correct 14 ms 11000 KB Output is correct
16 Correct 13 ms 10844 KB Output is correct
17 Correct 12 ms 10844 KB Output is correct
18 Correct 12 ms 11004 KB Output is correct
19 Correct 658 ms 66304 KB Output is correct
20 Correct 647 ms 66304 KB Output is correct
21 Correct 560 ms 66080 KB Output is correct
22 Correct 568 ms 66564 KB Output is correct
23 Correct 555 ms 66184 KB Output is correct
24 Correct 536 ms 66240 KB Output is correct
25 Correct 529 ms 66504 KB Output is correct
26 Correct 544 ms 66168 KB Output is correct
27 Correct 542 ms 66104 KB Output is correct
28 Correct 558 ms 66244 KB Output is correct
29 Correct 542 ms 66336 KB Output is correct
30 Correct 543 ms 66252 KB Output is correct
31 Correct 548 ms 66240 KB Output is correct
32 Correct 556 ms 66264 KB Output is correct
33 Correct 548 ms 66580 KB Output is correct
34 Correct 520 ms 66240 KB Output is correct
35 Correct 523 ms 66300 KB Output is correct
36 Correct 523 ms 66628 KB Output is correct
37 Correct 516 ms 66240 KB Output is correct
38 Correct 523 ms 66084 KB Output is correct
39 Correct 523 ms 66676 KB Output is correct
40 Correct 451 ms 49172 KB Output is correct
41 Correct 500 ms 66716 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 2 ms 8792 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 8 ms 10844 KB Output is correct
12 Correct 9 ms 10844 KB Output is correct
13 Correct 10 ms 10988 KB Output is correct
14 Correct 14 ms 10844 KB Output is correct
15 Correct 14 ms 11000 KB Output is correct
16 Correct 13 ms 10844 KB Output is correct
17 Correct 12 ms 10844 KB Output is correct
18 Correct 12 ms 11004 KB Output is correct
19 Runtime error 354 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -