Submission #479034

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
479034	2021-10-09T13:23:45 Z	Christopher_	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	8 / 100	3000 ms	19848 KB

sortbooks

#include <bits/stdc++.h>

using namespace std;

struct node {
	int mx;
};

vector<node> tree;
vector<int> a;

void Build(int x, int l, int r) {
	if (l == r) {
		tree[x].mx = a[l];
		return;
	}
	int m = (l + r) >> 1;
	Build((x << 1) + 1, l, m);
	Build((x << 1) + 2, m + 1, r);
	tree[x].mx = max(tree[(x << 1) + 1].mx, tree[(x << 1) + 2].mx);
}

void Build() {
	int n = (int) a.size();
	tree.resize(4 * n + 1);
	Build(0, 0, n - 1);
}

int Find(int x, int l, int r, int ll, int rr, int val) {
	if (rr < l || ll > r) return 0;
	else if (ll >= l && rr <= r && tree[x].mx < val) return tree[x].mx;
	else if (ll >= l && rr <= r && ll == rr) return 0;
	int m = (ll + rr) >> 1;
	int left = Find((x << 1) + 1, l, r, ll, m, val);
	int right = Find((x << 1) + 2, l, r, m + 1, rr, val);
	return max(left, right);
}

int Find(int l, int r, int x) {
	int n = (int) a.size();
	return Find(0, l, r, 0, n - 1, x);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	a.resize(n);
	for (int &e : a) {
		cin >> e;
	}
	Build();
	while (q--) {
		bool ok = true;
		int l, r, c;
		cin >> l >> r >> c;
		--l, --r;
		for (int i = l; i < r; ++i) {
			if (a[i] > a[i + 1]) {
				int x = Find(i + 1, r, a[i]);
				//cout << "x" << x << '\n';
				if (x + a[i] > c) {
					cout << 0 << '\n';
					ok = false;
					break;
				}
			}
		}
		if (ok) cout << 1 << '\n';
	}
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	1 ms	208 KB	Output is correct
6	Correct	2 ms	336 KB	Output is correct
7	Correct	4 ms	324 KB	Output is correct
8	Correct	28 ms	336 KB	Output is correct
9	Correct	1 ms	208 KB	Output is correct
10	Correct	1 ms	316 KB	Output is correct

Subtask #2

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	1 ms	208 KB	Output is correct
6	Correct	2 ms	336 KB	Output is correct
7	Correct	4 ms	324 KB	Output is correct
8	Correct	28 ms	336 KB	Output is correct
9	Correct	1 ms	208 KB	Output is correct
10	Correct	1 ms	316 KB	Output is correct
11	Correct	35 ms	336 KB	Output is correct
12	Correct	217 ms	500 KB	Output is correct
13	Correct	168 ms	500 KB	Output is correct
14	Correct	349 ms	448 KB	Output is correct
15	Correct	223 ms	552 KB	Output is correct
16	Execution timed out	3061 ms	464 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #3

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	3066 ms	19848 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	3056 ms	2252 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	1 ms	208 KB	Output is correct
6	Correct	2 ms	336 KB	Output is correct
7	Correct	4 ms	324 KB	Output is correct
8	Correct	28 ms	336 KB	Output is correct
9	Correct	1 ms	208 KB	Output is correct
10	Correct	1 ms	316 KB	Output is correct
11	Correct	35 ms	336 KB	Output is correct
12	Correct	217 ms	500 KB	Output is correct
13	Correct	168 ms	500 KB	Output is correct
14	Correct	349 ms	448 KB	Output is correct
15	Correct	223 ms	552 KB	Output is correct
16	Execution timed out	3061 ms	464 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #6

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	1 ms	208 KB	Output is correct
6	Correct	2 ms	336 KB	Output is correct
7	Correct	4 ms	324 KB	Output is correct
8	Correct	28 ms	336 KB	Output is correct
9	Correct	1 ms	208 KB	Output is correct
10	Correct	1 ms	316 KB	Output is correct
11	Correct	35 ms	336 KB	Output is correct
12	Correct	217 ms	500 KB	Output is correct
13	Correct	168 ms	500 KB	Output is correct
14	Correct	349 ms	448 KB	Output is correct
15	Correct	223 ms	552 KB	Output is correct
16	Execution timed out	3061 ms	464 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-