oj.uz

답안 #479034

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
479034 2021-10-09T13:23:45 Z Christopher_ Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
8 / 100
 3000 ms 19848 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3066 ms 19848 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3056 ms 2252 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -