oj.uz

답안 #500773

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
500773 2022-01-01T08:56:49 Z Mazaalai Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 262144 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define LINE "----------------------\n"
#define ALL(x) x.begin(),x.end()
using namespace std;
using ll = long long;
using PII = pair <int, int>;
using VI = vector <int>;
using VVI = vector <VI>;
using VPI = vector <PII>;

const int N = 1e6 + 5;
const int M = 4 * N;
int nums[N];
struct Node {
	int maxInv;
	vector <int> vals;
	Node() {
		maxInv = -1;
	}
	void init(int l, int r) {
		int curMax = nums[l];
		vals.pb(nums[l]);
		for (int i = l+1; i <= r; i++) {
			vals.pb(nums[i]);
			if (nums[i] >= curMax) curMax = nums[i];
			else maxInv = max(maxInv, curMax+nums[i]);
		}
		sort(ALL(vals));
	}
	int findSmaller(int x) {
		int id = lower_bound(ALL(vals), x) - vals.begin();
		return (id ? vals[id-1] : -1);
	}
};
Node node[M];
int n, m;
void build(int l, int r, int head) {
	node[head].init(l, r);
	if (l == r) return;
	int mid = (l+r)>>1;
	build(l, mid, head*2+1);
	build(mid+1, r, head*2+2);
}
PII zero = {-1, -1};
bool done = 0;
int maxQuery(int l, int r, int L, int R, int mx, int head) { // returns MaxInv, ans maxEl
	if (done) return -1;
	if (l > R || L > r) return -1;
	if (L <= l && r <= R) {
		int ret = node[head].findSmaller(mx);
		done |= ret == mx-1;
		return ret;
	}
	int mid = (l+r)>>1;
	return max(
		maxQuery(l, mid, L, R, mx, head*2+1),
		maxQuery(mid+1, r, L, R, mx, head*2+2)
	);
}
PII query(int l, int r, int L, int R, int head) { // returns MaxInv, ans maxEl
	if (l > R || L > r) return zero;
	if (L <= l && r <= R) return {node[head].maxInv, node[head].vals.back()};
	int mid = (l+r)>>1;
	PII lhs = query(l, mid, L, R, head*2+1);
	PII rhs = query(mid+1, r, L, R, head*2+2);
	int maxAns = max(lhs.ff, rhs.ff);
	if (lhs.ss != -1) {
		done = 0;
		int mx = maxQuery(mid+1, r, L, R, lhs.ss, head*2+2);
		// int mx = node[head*2+2].findSmaller(lhs.ss);
		if (mx != -1) maxAns = max(maxAns, lhs.ss + mx);
	}
	return {maxAns, max(lhs.ss, rhs.ss)};
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> nums[i];
	build(1, n, 0);
	for (int i = 0; i < m; i++) {
		int l, r, k; cin >> l >> r >> k;
		// cout << LINE;
		int cur = query(1, n, l, r, 0).ff;
		// cout << l << ' ' << r << ' ' << cur << '\n';
		cout << (cur > k ? 0 : 1) << "\n";
	}

}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 125468 KB Output is correct
2 Correct 63 ms 125508 KB Output is correct
3 Correct 62 ms 125560 KB Output is correct
4 Correct 63 ms 125544 KB Output is correct
5 Correct 64 ms 125508 KB Output is correct
6 Correct 67 ms 125568 KB Output is correct
7 Correct 63 ms 125572 KB Output is correct
8 Correct 64 ms 125560 KB Output is correct
9 Correct 63 ms 125508 KB Output is correct
10 Correct 63 ms 125560 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 125468 KB Output is correct
2 Correct 63 ms 125508 KB Output is correct
3 Correct 62 ms 125560 KB Output is correct
4 Correct 63 ms 125544 KB Output is correct
5 Correct 64 ms 125508 KB Output is correct
6 Correct 67 ms 125568 KB Output is correct
7 Correct 63 ms 125572 KB Output is correct
8 Correct 64 ms 125560 KB Output is correct
9 Correct 63 ms 125508 KB Output is correct
10 Correct 63 ms 125560 KB Output is correct
11 Correct 68 ms 125704 KB Output is correct
12 Correct 70 ms 126156 KB Output is correct
13 Correct 70 ms 126100 KB Output is correct
14 Correct 76 ms 126140 KB Output is correct
15 Correct 73 ms 126192 KB Output is correct
16 Correct 71 ms 126156 KB Output is correct
17 Correct 67 ms 125952 KB Output is correct
18 Correct 70 ms 126132 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 368 ms 139316 KB Output is correct
2 Correct 379 ms 139252 KB Output is correct
3 Correct 332 ms 139412 KB Output is correct
4 Correct 327 ms 139360 KB Output is correct
5 Correct 322 ms 139216 KB Output is correct
6 Correct 330 ms 139240 KB Output is correct
7 Correct 338 ms 139352 KB Output is correct
8 Correct 268 ms 139208 KB Output is correct
9 Correct 110 ms 125764 KB Output is correct
10 Correct 279 ms 139324 KB Output is correct

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 125468 KB Output is correct
2 Correct 63 ms 125508 KB Output is correct
3 Correct 62 ms 125560 KB Output is correct
4 Correct 63 ms 125544 KB Output is correct
5 Correct 64 ms 125508 KB Output is correct
6 Correct 67 ms 125568 KB Output is correct
7 Correct 63 ms 125572 KB Output is correct
8 Correct 64 ms 125560 KB Output is correct
9 Correct 63 ms 125508 KB Output is correct
10 Correct 63 ms 125560 KB Output is correct
11 Correct 68 ms 125704 KB Output is correct
12 Correct 70 ms 126156 KB Output is correct
13 Correct 70 ms 126100 KB Output is correct
14 Correct 76 ms 126140 KB Output is correct
15 Correct 73 ms 126192 KB Output is correct
16 Correct 71 ms 126156 KB Output is correct
17 Correct 67 ms 125952 KB Output is correct
18 Correct 70 ms 126132 KB Output is correct
19 Correct 822 ms 153772 KB Output is correct
20 Correct 819 ms 154188 KB Output is correct
21 Correct 835 ms 153952 KB Output is correct
22 Correct 845 ms 153876 KB Output is correct
23 Correct 832 ms 153916 KB Output is correct
24 Correct 657 ms 153932 KB Output is correct
25 Correct 661 ms 153852 KB Output is correct
26 Correct 736 ms 153880 KB Output is correct
27 Correct 728 ms 153912 KB Output is correct
28 Correct 722 ms 153992 KB Output is correct
29 Correct 679 ms 154072 KB Output is correct
30 Correct 752 ms 153800 KB Output is correct
31 Correct 699 ms 153844 KB Output is correct
32 Correct 697 ms 153920 KB Output is correct
33 Correct 705 ms 153880 KB Output is correct
34 Correct 656 ms 153860 KB Output is correct
35 Correct 656 ms 154104 KB Output is correct
36 Correct 669 ms 153920 KB Output is correct
37 Correct 664 ms 153892 KB Output is correct
38 Correct 668 ms 153872 KB Output is correct
39 Correct 630 ms 153844 KB Output is correct
40 Correct 407 ms 141928 KB Output is correct
41 Correct 548 ms 153860 KB Output is correct

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 125468 KB Output is correct
2 Correct 63 ms 125508 KB Output is correct
3 Correct 62 ms 125560 KB Output is correct
4 Correct 63 ms 125544 KB Output is correct
5 Correct 64 ms 125508 KB Output is correct
6 Correct 67 ms 125568 KB Output is correct
7 Correct 63 ms 125572 KB Output is correct
8 Correct 64 ms 125560 KB Output is correct
9 Correct 63 ms 125508 KB Output is correct
10 Correct 63 ms 125560 KB Output is correct
11 Correct 68 ms 125704 KB Output is correct
12 Correct 70 ms 126156 KB Output is correct
13 Correct 70 ms 126100 KB Output is correct
14 Correct 76 ms 126140 KB Output is correct
15 Correct 73 ms 126192 KB Output is correct
16 Correct 71 ms 126156 KB Output is correct
17 Correct 67 ms 125952 KB Output is correct
18 Correct 70 ms 126132 KB Output is correct
19 Execution timed out 3034 ms 262144 KB Time limit exceeded
20 Halted 0 ms 0 KB -