oj.uz

답안 #500772

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
500772 2022-01-01T08:52:34 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() {
	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 77 ms 125508 KB Output is correct
2 Correct 80 ms 125508 KB Output is correct
3 Correct 62 ms 125480 KB Output is correct
4 Correct 62 ms 125548 KB Output is correct
5 Correct 64 ms 125484 KB Output is correct
6 Correct 66 ms 125672 KB Output is correct
7 Correct 80 ms 125528 KB Output is correct
8 Correct 62 ms 125516 KB Output is correct
9 Correct 65 ms 125576 KB Output is correct
10 Correct 63 ms 125508 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 125508 KB Output is correct
2 Correct 80 ms 125508 KB Output is correct
3 Correct 62 ms 125480 KB Output is correct
4 Correct 62 ms 125548 KB Output is correct
5 Correct 64 ms 125484 KB Output is correct
6 Correct 66 ms 125672 KB Output is correct
7 Correct 80 ms 125528 KB Output is correct
8 Correct 62 ms 125516 KB Output is correct
9 Correct 65 ms 125576 KB Output is correct
10 Correct 63 ms 125508 KB Output is correct
11 Correct 68 ms 125764 KB Output is correct
12 Correct 75 ms 126284 KB Output is correct
13 Correct 69 ms 126260 KB Output is correct
14 Correct 73 ms 126260 KB Output is correct
15 Correct 74 ms 126344 KB Output is correct
16 Correct 72 ms 126300 KB Output is correct
17 Correct 82 ms 126068 KB Output is correct
18 Correct 80 ms 126276 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 379 ms 140576 KB Output is correct
2 Correct 401 ms 140496 KB Output is correct
3 Correct 328 ms 140480 KB Output is correct
4 Correct 403 ms 140580 KB Output is correct
5 Correct 317 ms 140688 KB Output is correct
6 Correct 345 ms 140604 KB Output is correct
7 Correct 326 ms 140572 KB Output is correct
8 Correct 288 ms 140584 KB Output is correct
9 Correct 117 ms 127036 KB Output is correct
10 Correct 291 ms 140540 KB Output is correct

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 125508 KB Output is correct
2 Correct 80 ms 125508 KB Output is correct
3 Correct 62 ms 125480 KB Output is correct
4 Correct 62 ms 125548 KB Output is correct
5 Correct 64 ms 125484 KB Output is correct
6 Correct 66 ms 125672 KB Output is correct
7 Correct 80 ms 125528 KB Output is correct
8 Correct 62 ms 125516 KB Output is correct
9 Correct 65 ms 125576 KB Output is correct
10 Correct 63 ms 125508 KB Output is correct
11 Correct 68 ms 125764 KB Output is correct
12 Correct 75 ms 126284 KB Output is correct
13 Correct 69 ms 126260 KB Output is correct
14 Correct 73 ms 126260 KB Output is correct
15 Correct 74 ms 126344 KB Output is correct
16 Correct 72 ms 126300 KB Output is correct
17 Correct 82 ms 126068 KB Output is correct
18 Correct 80 ms 126276 KB Output is correct
19 Correct 818 ms 155224 KB Output is correct
20 Correct 936 ms 155216 KB Output is correct
21 Correct 897 ms 155176 KB Output is correct
22 Correct 817 ms 155160 KB Output is correct
23 Correct 864 ms 155168 KB Output is correct
24 Correct 735 ms 155148 KB Output is correct
25 Correct 675 ms 155144 KB Output is correct
26 Correct 739 ms 155264 KB Output is correct
27 Correct 705 ms 155164 KB Output is correct
28 Correct 773 ms 155168 KB Output is correct
29 Correct 717 ms 155100 KB Output is correct
30 Correct 726 ms 155120 KB Output is correct
31 Correct 776 ms 155160 KB Output is correct
32 Correct 866 ms 154796 KB Output is correct
33 Correct 731 ms 154788 KB Output is correct
34 Correct 697 ms 154560 KB Output is correct
35 Correct 668 ms 154388 KB Output is correct
36 Correct 685 ms 154548 KB Output is correct
37 Correct 699 ms 154248 KB Output is correct
38 Correct 710 ms 154016 KB Output is correct
39 Correct 717 ms 154000 KB Output is correct
40 Correct 418 ms 142128 KB Output is correct
41 Correct 565 ms 153760 KB Output is correct

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 125508 KB Output is correct
2 Correct 80 ms 125508 KB Output is correct
3 Correct 62 ms 125480 KB Output is correct
4 Correct 62 ms 125548 KB Output is correct
5 Correct 64 ms 125484 KB Output is correct
6 Correct 66 ms 125672 KB Output is correct
7 Correct 80 ms 125528 KB Output is correct
8 Correct 62 ms 125516 KB Output is correct
9 Correct 65 ms 125576 KB Output is correct
10 Correct 63 ms 125508 KB Output is correct
11 Correct 68 ms 125764 KB Output is correct
12 Correct 75 ms 126284 KB Output is correct
13 Correct 69 ms 126260 KB Output is correct
14 Correct 73 ms 126260 KB Output is correct
15 Correct 74 ms 126344 KB Output is correct
16 Correct 72 ms 126300 KB Output is correct
17 Correct 82 ms 126068 KB Output is correct
18 Correct 80 ms 126276 KB Output is correct
19 Execution timed out 3079 ms 262144 KB Time limit exceeded
20 Halted 0 ms 0 KB -