oj.uz

Submission #500771

# Submission time Handle Problem Language Result Execution time Memory
500771 2022-01-01T08:51:30 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};
int maxQuery(int l, int r, int L, int R, int mx, int head) { // returns MaxInv, ans maxEl
	if (l > R || L > r) return -1;
	if (L <= l && r <= R) return node[head].findSmaller(mx);
	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) {
		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() {
	// 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

# Verdict Execution time Memory Grader output
1 Correct 61 ms 125520 KB Output is correct
2 Correct 58 ms 125608 KB Output is correct
3 Correct 67 ms 125492 KB Output is correct
4 Correct 68 ms 125476 KB Output is correct
5 Correct 73 ms 125508 KB Output is correct
6 Correct 65 ms 125476 KB Output is correct
7 Correct 66 ms 125636 KB Output is correct
8 Correct 61 ms 125508 KB Output is correct
9 Correct 61 ms 125508 KB Output is correct
10 Correct 61 ms 125504 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 125520 KB Output is correct
2 Correct 58 ms 125608 KB Output is correct
3 Correct 67 ms 125492 KB Output is correct
4 Correct 68 ms 125476 KB Output is correct
5 Correct 73 ms 125508 KB Output is correct
6 Correct 65 ms 125476 KB Output is correct
7 Correct 66 ms 125636 KB Output is correct
8 Correct 61 ms 125508 KB Output is correct
9 Correct 61 ms 125508 KB Output is correct
10 Correct 61 ms 125504 KB Output is correct
11 Correct 70 ms 125668 KB Output is correct
12 Correct 81 ms 126244 KB Output is correct
13 Correct 78 ms 126220 KB Output is correct
14 Correct 81 ms 126304 KB Output is correct
15 Correct 80 ms 126320 KB Output is correct
16 Correct 76 ms 126280 KB Output is correct
17 Correct 74 ms 126008 KB Output is correct
18 Correct 76 ms 126176 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 553 ms 141240 KB Output is correct
2 Correct 615 ms 141140 KB Output is correct
3 Correct 585 ms 141196 KB Output is correct
4 Correct 553 ms 141184 KB Output is correct
5 Correct 489 ms 141248 KB Output is correct
6 Correct 516 ms 141124 KB Output is correct
7 Correct 534 ms 140944 KB Output is correct
8 Correct 476 ms 140876 KB Output is correct
9 Correct 268 ms 127044 KB Output is correct
10 Correct 486 ms 140880 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 125520 KB Output is correct
2 Correct 58 ms 125608 KB Output is correct
3 Correct 67 ms 125492 KB Output is correct
4 Correct 68 ms 125476 KB Output is correct
5 Correct 73 ms 125508 KB Output is correct
6 Correct 65 ms 125476 KB Output is correct
7 Correct 66 ms 125636 KB Output is correct
8 Correct 61 ms 125508 KB Output is correct
9 Correct 61 ms 125508 KB Output is correct
10 Correct 61 ms 125504 KB Output is correct
11 Correct 70 ms 125668 KB Output is correct
12 Correct 81 ms 126244 KB Output is correct
13 Correct 78 ms 126220 KB Output is correct
14 Correct 81 ms 126304 KB Output is correct
15 Correct 80 ms 126320 KB Output is correct
16 Correct 76 ms 126280 KB Output is correct
17 Correct 74 ms 126008 KB Output is correct
18 Correct 76 ms 126176 KB Output is correct
19 Correct 1341 ms 160272 KB Output is correct
20 Correct 1273 ms 160388 KB Output is correct
21 Correct 1286 ms 160220 KB Output is correct
22 Correct 1342 ms 160332 KB Output is correct
23 Correct 1326 ms 160160 KB Output is correct
24 Correct 1057 ms 160172 KB Output is correct
25 Correct 1066 ms 160020 KB Output is correct
26 Correct 1238 ms 160308 KB Output is correct
27 Correct 1177 ms 160252 KB Output is correct
28 Correct 1211 ms 160344 KB Output is correct
29 Correct 1129 ms 160400 KB Output is correct
30 Correct 1106 ms 160440 KB Output is correct
31 Correct 1146 ms 160448 KB Output is correct
32 Correct 1148 ms 160528 KB Output is correct
33 Correct 1185 ms 160372 KB Output is correct
34 Correct 1124 ms 160204 KB Output is correct
35 Correct 1046 ms 160160 KB Output is correct
36 Correct 1065 ms 159776 KB Output is correct
37 Correct 1098 ms 160012 KB Output is correct
38 Correct 1108 ms 159976 KB Output is correct
39 Correct 1086 ms 158944 KB Output is correct
40 Correct 812 ms 146296 KB Output is correct
41 Correct 1031 ms 158520 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 125520 KB Output is correct
2 Correct 58 ms 125608 KB Output is correct
3 Correct 67 ms 125492 KB Output is correct
4 Correct 68 ms 125476 KB Output is correct
5 Correct 73 ms 125508 KB Output is correct
6 Correct 65 ms 125476 KB Output is correct
7 Correct 66 ms 125636 KB Output is correct
8 Correct 61 ms 125508 KB Output is correct
9 Correct 61 ms 125508 KB Output is correct
10 Correct 61 ms 125504 KB Output is correct
11 Correct 70 ms 125668 KB Output is correct
12 Correct 81 ms 126244 KB Output is correct
13 Correct 78 ms 126220 KB Output is correct
14 Correct 81 ms 126304 KB Output is correct
15 Correct 80 ms 126320 KB Output is correct
16 Correct 76 ms 126280 KB Output is correct
17 Correct 74 ms 126008 KB Output is correct
18 Correct 76 ms 126176 KB Output is correct
19 Execution timed out 3033 ms 262144 KB Time limit exceeded
20 Halted 0 ms 0 KB -