oj.uz

Submission #798267

# Submission time Handle Problem Language Result Execution time Memory
798267 2023-07-30T14:30:02 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
34 / 100
 1511 ms 216888 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 mnw;
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;
	for (int i=0; i<n; i++) cin >> w[i];

	mnw = 1e9+3;
	for (int i=0; i<n; i++) mnw = min(mnw, 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;
		if (k < mnw) cout << (l == r) << '\n';
		else cout << (query1(0, n-1, 1, l-1, r-1) <= k) << '\n';
	}
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37872 KB Output is correct
2 Correct 20 ms 37876 KB Output is correct
3 Correct 19 ms 37844 KB Output is correct
4 Correct 22 ms 37940 KB Output is correct
5 Correct 23 ms 37920 KB Output is correct
6 Correct 22 ms 38064 KB Output is correct
7 Correct 22 ms 38072 KB Output is correct
8 Correct 22 ms 38088 KB Output is correct
9 Correct 21 ms 37988 KB Output is correct
10 Correct 21 ms 37860 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37872 KB Output is correct
2 Correct 20 ms 37876 KB Output is correct
3 Correct 19 ms 37844 KB Output is correct
4 Correct 22 ms 37940 KB Output is correct
5 Correct 23 ms 37920 KB Output is correct
6 Correct 22 ms 38064 KB Output is correct
7 Correct 22 ms 38072 KB Output is correct
8 Correct 22 ms 38088 KB Output is correct
9 Correct 21 ms 37988 KB Output is correct
10 Correct 21 ms 37860 KB Output is correct
11 Correct 25 ms 38620 KB Output is correct
12 Correct 32 ms 40928 KB Output is correct
13 Correct 31 ms 41000 KB Output is correct
14 Correct 36 ms 41124 KB Output is correct
15 Correct 35 ms 41088 KB Output is correct
16 Correct 36 ms 41172 KB Output is correct
17 Correct 31 ms 40460 KB Output is correct
18 Correct 25 ms 38460 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 69 ms 78292 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 91844 KB Output is correct
2 Correct 454 ms 91828 KB Output is correct
3 Correct 290 ms 49564 KB Output is correct
4 Correct 275 ms 49580 KB Output is correct
5 Correct 274 ms 49864 KB Output is correct
6 Correct 287 ms 49576 KB Output is correct
7 Correct 291 ms 49620 KB Output is correct
8 Correct 190 ms 48860 KB Output is correct
9 Correct 66 ms 38320 KB Output is correct
10 Correct 192 ms 48864 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37872 KB Output is correct
2 Correct 20 ms 37876 KB Output is correct
3 Correct 19 ms 37844 KB Output is correct
4 Correct 22 ms 37940 KB Output is correct
5 Correct 23 ms 37920 KB Output is correct
6 Correct 22 ms 38064 KB Output is correct
7 Correct 22 ms 38072 KB Output is correct
8 Correct 22 ms 38088 KB Output is correct
9 Correct 21 ms 37988 KB Output is correct
10 Correct 21 ms 37860 KB Output is correct
11 Correct 25 ms 38620 KB Output is correct
12 Correct 32 ms 40928 KB Output is correct
13 Correct 31 ms 41000 KB Output is correct
14 Correct 36 ms 41124 KB Output is correct
15 Correct 35 ms 41088 KB Output is correct
16 Correct 36 ms 41172 KB Output is correct
17 Correct 31 ms 40460 KB Output is correct
18 Correct 25 ms 38460 KB Output is correct
19 Correct 1511 ms 216880 KB Output is correct
20 Correct 1492 ms 216752 KB Output is correct
21 Correct 1269 ms 216752 KB Output is correct
22 Correct 1259 ms 216832 KB Output is correct
23 Correct 1266 ms 216888 KB Output is correct
24 Incorrect 1456 ms 216748 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37872 KB Output is correct
2 Correct 20 ms 37876 KB Output is correct
3 Correct 19 ms 37844 KB Output is correct
4 Correct 22 ms 37940 KB Output is correct
5 Correct 23 ms 37920 KB Output is correct
6 Correct 22 ms 38064 KB Output is correct
7 Correct 22 ms 38072 KB Output is correct
8 Correct 22 ms 38088 KB Output is correct
9 Correct 21 ms 37988 KB Output is correct
10 Correct 21 ms 37860 KB Output is correct
11 Correct 25 ms 38620 KB Output is correct
12 Correct 32 ms 40928 KB Output is correct
13 Correct 31 ms 41000 KB Output is correct
14 Correct 36 ms 41124 KB Output is correct
15 Correct 35 ms 41088 KB Output is correct
16 Correct 36 ms 41172 KB Output is correct
17 Correct 31 ms 40460 KB Output is correct
18 Correct 25 ms 38460 KB Output is correct
19 Runtime error 69 ms 78292 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -