oj.uz

Submission #572108

# Submission time Handle Problem Language Result Execution time Memory
572108 2022-06-03T16:21:20 Z vovamr Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 744 ms 262144 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int N = (1 << 20) + 5;

ve<int> t[2 * N];
int mx[2 * N], a[N], answer[2 * N];

inline void build(int v, int vl, int vr) {
	if (vl == vr) {
		mx[v] = a[vl];
		t[v] = ve<int>(1, a[vl]);
		answer[v] = 0;
		return;
	}
	int m = vl + vr >> 1;
	build(2 * v + 1, vl, m);
	build(2 * v + 2, m + 1, vr);
	mx[v] = max(mx[2 * v + 1], mx[2 * v + 2]);
	answer[v] = max(answer[2 * v + 1], answer[2 * v + 2]);
	merge(all(t[2 * v + 1]), all(t[2 * v + 2]), back_inserter(t[v]));
	int ps = lower_bound(all(t[2 * v + 2]), mx[2 * v + 1]) - t[2 * v + 2].begin();
	if (ps != 0) { --ps; chmax(answer[v], mx[2 * v + 1] + t[2 * v + 2][ps]); }
}

inline void get(int v, int vl, int vr, int l, int r, ve<int> &pos) {
	if (l > r) return;
	else if (vl == l && vr == r) return void(pos.pb(v));
	int m = vl + vr >> 1;
	get(2 * v + 1, vl, m, l, min(r, m), pos);
	get(2 * v + 2, m + 1, vr, max(l, m + 1), r, pos);
}

ve<pii> z[2 * N];

inline void solve() {
	int n, q;
	cin >> n >> q;
	for (int i = 0; i < n; ++i) cin >> a[i];

	build(0, 0, n - 1);

	ve<pii> lel(q);

	for (int i = 0; i < q; ++i) {
		int l, r, k;
		cin >> l >> r >> k, --l, --r;

		lel[i].se = k;

		ve<int> pos;
		get(0, 0, n - 1, l, r, pos);

		int amx = mx[pos[0]], res = answer[pos[0]];

		for (int j = 1; j < sz(pos); ++j) {
			int v = pos[j];
			z[v].pb({amx, i});

			chmax(res, answer[v]);
			chmax(amx, mx[v]);
		}
		lel[i].fi = res;
	}
	for (int v = 0; v < 4 * n; ++v) {

		sort(all(z[v]));

		int ptr = 0;
		for (auto &[num, id] : z[v]) {
			while (ptr < sz(t[v]) && t[v][ptr] < num) ++ptr;
			if (ptr > 0) chmax(lel[id].fi, num + t[v][ptr - 1]);
		}
	}

	for (int i = 0; i < q; ++i) cout << (lel[i].se >= lel[i].fi ? 1 : 0) << '\n';
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Compilation message

sortbooks.cpp: In function 'void build(int, int, int)':
sortbooks.cpp:35:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |  int m = vl + vr >> 1;
      |          ~~~^~~~
sortbooks.cpp: In function 'void get(int, int, int, int, int, std::vector<int>&)':
sortbooks.cpp:48:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |  int m = vl + vr >> 1;
      |          ~~~^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 98764 KB Output is correct
2 Correct 45 ms 98744 KB Output is correct
3 Correct 48 ms 98816 KB Output is correct
4 Correct 47 ms 98868 KB Output is correct
5 Correct 46 ms 98772 KB Output is correct
6 Correct 55 ms 98840 KB Output is correct
7 Correct 49 ms 98888 KB Output is correct
8 Correct 47 ms 98932 KB Output is correct
9 Correct 49 ms 98800 KB Output is correct
10 Correct 45 ms 98844 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 98764 KB Output is correct
2 Correct 45 ms 98744 KB Output is correct
3 Correct 48 ms 98816 KB Output is correct
4 Correct 47 ms 98868 KB Output is correct
5 Correct 46 ms 98772 KB Output is correct
6 Correct 55 ms 98840 KB Output is correct
7 Correct 49 ms 98888 KB Output is correct
8 Correct 47 ms 98932 KB Output is correct
9 Correct 49 ms 98800 KB Output is correct
10 Correct 45 ms 98844 KB Output is correct
11 Correct 50 ms 99300 KB Output is correct
12 Correct 54 ms 99952 KB Output is correct
13 Correct 55 ms 100040 KB Output is correct
14 Correct 62 ms 100376 KB Output is correct
15 Correct 56 ms 100368 KB Output is correct
16 Correct 54 ms 100172 KB Output is correct
17 Correct 54 ms 99636 KB Output is correct
18 Correct 58 ms 100056 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 508 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 131404 KB Output is correct
2 Correct 274 ms 132388 KB Output is correct
3 Correct 284 ms 133252 KB Output is correct
4 Correct 274 ms 131668 KB Output is correct
5 Correct 290 ms 131248 KB Output is correct
6 Correct 252 ms 135756 KB Output is correct
7 Correct 252 ms 135856 KB Output is correct
8 Correct 241 ms 127440 KB Output is correct
9 Correct 121 ms 103732 KB Output is correct
10 Correct 230 ms 127516 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 98764 KB Output is correct
2 Correct 45 ms 98744 KB Output is correct
3 Correct 48 ms 98816 KB Output is correct
4 Correct 47 ms 98868 KB Output is correct
5 Correct 46 ms 98772 KB Output is correct
6 Correct 55 ms 98840 KB Output is correct
7 Correct 49 ms 98888 KB Output is correct
8 Correct 47 ms 98932 KB Output is correct
9 Correct 49 ms 98800 KB Output is correct
10 Correct 45 ms 98844 KB Output is correct
11 Correct 50 ms 99300 KB Output is correct
12 Correct 54 ms 99952 KB Output is correct
13 Correct 55 ms 100040 KB Output is correct
14 Correct 62 ms 100376 KB Output is correct
15 Correct 56 ms 100368 KB Output is correct
16 Correct 54 ms 100172 KB Output is correct
17 Correct 54 ms 99636 KB Output is correct
18 Correct 58 ms 100056 KB Output is correct
19 Correct 744 ms 165980 KB Output is correct
20 Correct 707 ms 165464 KB Output is correct
21 Correct 578 ms 169320 KB Output is correct
22 Correct 613 ms 168892 KB Output is correct
23 Correct 631 ms 168776 KB Output is correct
24 Correct 519 ms 171156 KB Output is correct
25 Correct 509 ms 171080 KB Output is correct
26 Correct 587 ms 172500 KB Output is correct
27 Correct 611 ms 172488 KB Output is correct
28 Correct 627 ms 167260 KB Output is correct
29 Correct 662 ms 164620 KB Output is correct
30 Correct 609 ms 164640 KB Output is correct
31 Correct 642 ms 165048 KB Output is correct
32 Correct 620 ms 164976 KB Output is correct
33 Correct 594 ms 165052 KB Output is correct
34 Correct 492 ms 181156 KB Output is correct
35 Correct 509 ms 181024 KB Output is correct
36 Correct 522 ms 180884 KB Output is correct
37 Correct 523 ms 181360 KB Output is correct
38 Correct 504 ms 181252 KB Output is correct
39 Correct 521 ms 163988 KB Output is correct
40 Correct 359 ms 138944 KB Output is correct
41 Correct 528 ms 160996 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 98764 KB Output is correct
2 Correct 45 ms 98744 KB Output is correct
3 Correct 48 ms 98816 KB Output is correct
4 Correct 47 ms 98868 KB Output is correct
5 Correct 46 ms 98772 KB Output is correct
6 Correct 55 ms 98840 KB Output is correct
7 Correct 49 ms 98888 KB Output is correct
8 Correct 47 ms 98932 KB Output is correct
9 Correct 49 ms 98800 KB Output is correct
10 Correct 45 ms 98844 KB Output is correct
11 Correct 50 ms 99300 KB Output is correct
12 Correct 54 ms 99952 KB Output is correct
13 Correct 55 ms 100040 KB Output is correct
14 Correct 62 ms 100376 KB Output is correct
15 Correct 56 ms 100368 KB Output is correct
16 Correct 54 ms 100172 KB Output is correct
17 Correct 54 ms 99636 KB Output is correct
18 Correct 58 ms 100056 KB Output is correct
19 Runtime error 508 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -