oj.uz

Submission #798270

# Submission time Handle Problem Language Result Execution time Memory
798270 2023-07-30T14:32:28 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 1794 ms 216948 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5+3, maxm = 2e5+3, maxw = 1e9+3;
int n, m;
int w[maxn];
int mxsum[4*maxn];
set<int> els[4*maxn];

void build(int l, int r, int v) {
	if (l == r) {
		mxsum[v] = -1;
		els[v].insert(-w[l]);
	} else {
		int mid = (l+r)/2;
		build(l, mid, v*2);
		build(mid+1, r, v*2+1);
		auto it = els[v*2+1].upper_bound(*els[v*2].begin());
		mxsum[v] = max({mxsum[v*2], mxsum[v*2+1], (it == els[v*2+1].end() ? -1 : -*els[v*2].begin() - *it)});
		for (int x : els[v*2]) els[v].insert(x);
		for (int x : els[v*2+1]) els[v].insert(x);
	}
}

int query2(int l, int r, int v, int lb, int rb) {
	if (r < lb || l > rb) return -1;
	if (l >= lb && r <= rb) return -*els[v].begin();
	int mid = (l+r)/2;
	return max(query2(l, mid, v*2, lb, rb), query2(mid+1, r, v*2+1, lb, rb));
}

int query3(int l, int r, int v, int lb, int rb, int k) {
	if (r < lb || l > rb) return -1;
	if (l >= lb && r <= rb) {
		auto it = els[v].upper_bound(-k);
		return (it == els[v].end() ? -1 : -*it);
	}
	int mid = (l+r)/2;
	return max(query3(l, mid, v*2, lb, rb, k), query3(mid+1, r, v*2+1, lb, rb, k));
}

int query1(int l, int r, int v, int lb, int rb) {
	if (r < lb || l > rb) return -1;
	if (l >= lb && r <= rb) return mxsum[v];
	int mid = (l+r)/2;
	int mxl = -1, mxr = -1;
	mxl = query2(l, mid, v*2, lb, mid);
	if (mxl != -1) mxr = query3(mid+1, r, v*2+1, mid+1, rb, mxl);
	return max({
		query1(l, mid, v*2, lb, rb),
		query1(mid+1, r, v*2+1, lb, rb),
		(mxr == -1 ? -1 : mxl + mxr)
	});
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	if (n <= maxn) {
		for (int i=0; i<n; i++) cin >> w[i];

		build(0, n-1, 1);

		// for (int i=0; i<n; i++) {
		// 	for (int j=i; j<n; j++) {
		// 		cout << i << ' ' << j << ' ' << query1(0, n-1, 1, i, j) << '\n';
		// 	}
		// }

		while (m--) {
			int l, r, k;
			cin >> l >> r >> k;
			
			cout << (query1(0, n-1, 1, l-1, r-1) <= k) << '\n';
		}

	} else {
		for (int i=0; i<n; i++) cin >> w[0];
		while (m--) {
			int l, r, k;
			cin >> l >> r >> k;
			cout << (l == r) << '\n';
		}
	}

	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37844 KB Output is correct
2 Correct 18 ms 37896 KB Output is correct
3 Correct 18 ms 37848 KB Output is correct
4 Correct 18 ms 37844 KB Output is correct
5 Correct 18 ms 37928 KB Output is correct
6 Correct 20 ms 38132 KB Output is correct
7 Correct 19 ms 38148 KB Output is correct
8 Correct 20 ms 38100 KB Output is correct
9 Correct 18 ms 38020 KB Output is correct
10 Correct 18 ms 37880 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37844 KB Output is correct
2 Correct 18 ms 37896 KB Output is correct
3 Correct 18 ms 37848 KB Output is correct
4 Correct 18 ms 37844 KB Output is correct
5 Correct 18 ms 37928 KB Output is correct
6 Correct 20 ms 38132 KB Output is correct
7 Correct 19 ms 38148 KB Output is correct
8 Correct 20 ms 38100 KB Output is correct
9 Correct 18 ms 38020 KB Output is correct
10 Correct 18 ms 37880 KB Output is correct
11 Correct 27 ms 38704 KB Output is correct
12 Correct 29 ms 40916 KB Output is correct
13 Correct 30 ms 41012 KB Output is correct
14 Correct 33 ms 41004 KB Output is correct
15 Correct 34 ms 41136 KB Output is correct
16 Correct 31 ms 41040 KB Output is correct
17 Correct 27 ms 40348 KB Output is correct
18 Correct 23 ms 38428 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 354 ms 69508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 91848 KB Output is correct
2 Correct 461 ms 91872 KB Output is correct
3 Correct 282 ms 49584 KB Output is correct
4 Correct 288 ms 49748 KB Output is correct
5 Correct 252 ms 49536 KB Output is correct
6 Correct 281 ms 49616 KB Output is correct
7 Correct 286 ms 49616 KB Output is correct
8 Correct 191 ms 48848 KB Output is correct
9 Correct 78 ms 38288 KB Output is correct
10 Correct 203 ms 48776 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37844 KB Output is correct
2 Correct 18 ms 37896 KB Output is correct
3 Correct 18 ms 37848 KB Output is correct
4 Correct 18 ms 37844 KB Output is correct
5 Correct 18 ms 37928 KB Output is correct
6 Correct 20 ms 38132 KB Output is correct
7 Correct 19 ms 38148 KB Output is correct
8 Correct 20 ms 38100 KB Output is correct
9 Correct 18 ms 38020 KB Output is correct
10 Correct 18 ms 37880 KB Output is correct
11 Correct 27 ms 38704 KB Output is correct
12 Correct 29 ms 40916 KB Output is correct
13 Correct 30 ms 41012 KB Output is correct
14 Correct 33 ms 41004 KB Output is correct
15 Correct 34 ms 41136 KB Output is correct
16 Correct 31 ms 41040 KB Output is correct
17 Correct 27 ms 40348 KB Output is correct
18 Correct 23 ms 38428 KB Output is correct
19 Correct 1506 ms 216672 KB Output is correct
20 Correct 1493 ms 216712 KB Output is correct
21 Correct 1249 ms 216652 KB Output is correct
22 Correct 1250 ms 216676 KB Output is correct
23 Correct 1294 ms 216632 KB Output is correct
24 Correct 1450 ms 216640 KB Output is correct
25 Correct 1473 ms 216696 KB Output is correct
26 Correct 1679 ms 216700 KB Output is correct
27 Correct 1690 ms 216948 KB Output is correct
28 Correct 1708 ms 216756 KB Output is correct
29 Correct 1759 ms 216800 KB Output is correct
30 Correct 1761 ms 216692 KB Output is correct
31 Correct 1777 ms 216840 KB Output is correct
32 Correct 1794 ms 216872 KB Output is correct
33 Correct 1769 ms 216876 KB Output is correct
34 Correct 1443 ms 216824 KB Output is correct
35 Correct 1433 ms 216824 KB Output is correct
36 Correct 1425 ms 216772 KB Output is correct
37 Correct 1430 ms 216852 KB Output is correct
38 Correct 1408 ms 216840 KB Output is correct
39 Correct 1435 ms 216852 KB Output is correct
40 Correct 810 ms 150804 KB Output is correct
41 Correct 434 ms 59956 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37844 KB Output is correct
2 Correct 18 ms 37896 KB Output is correct
3 Correct 18 ms 37848 KB Output is correct
4 Correct 18 ms 37844 KB Output is correct
5 Correct 18 ms 37928 KB Output is correct
6 Correct 20 ms 38132 KB Output is correct
7 Correct 19 ms 38148 KB Output is correct
8 Correct 20 ms 38100 KB Output is correct
9 Correct 18 ms 38020 KB Output is correct
10 Correct 18 ms 37880 KB Output is correct
11 Correct 27 ms 38704 KB Output is correct
12 Correct 29 ms 40916 KB Output is correct
13 Correct 30 ms 41012 KB Output is correct
14 Correct 33 ms 41004 KB Output is correct
15 Correct 34 ms 41136 KB Output is correct
16 Correct 31 ms 41040 KB Output is correct
17 Correct 27 ms 40348 KB Output is correct
18 Correct 23 ms 38428 KB Output is correct
19 Incorrect 354 ms 69508 KB Output isn't correct
20 Halted 0 ms 0 KB -