oj.uz

Submission #572107

# Submission time Handle Problem Language Result Execution time Memory
572107 2022-06-03T16:19:24 Z vovamr Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
34 / 100
 808 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 = 1e6 + 100;

ve<int> t[4 * N];
int mx[4 * N], a[N], answer[4 * 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[4 * 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 87 ms 188172 KB Output is correct
2 Correct 96 ms 188088 KB Output is correct
3 Correct 90 ms 188172 KB Output is correct
4 Correct 96 ms 188132 KB Output is correct
5 Correct 87 ms 188204 KB Output is correct
6 Correct 90 ms 188248 KB Output is correct
7 Correct 86 ms 188236 KB Output is correct
8 Correct 88 ms 188204 KB Output is correct
9 Correct 91 ms 188180 KB Output is correct
10 Correct 85 ms 188212 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 188172 KB Output is correct
2 Correct 96 ms 188088 KB Output is correct
3 Correct 90 ms 188172 KB Output is correct
4 Correct 96 ms 188132 KB Output is correct
5 Correct 87 ms 188204 KB Output is correct
6 Correct 90 ms 188248 KB Output is correct
7 Correct 86 ms 188236 KB Output is correct
8 Correct 88 ms 188204 KB Output is correct
9 Correct 91 ms 188180 KB Output is correct
10 Correct 85 ms 188212 KB Output is correct
11 Correct 91 ms 188760 KB Output is correct
12 Correct 95 ms 189364 KB Output is correct
13 Correct 96 ms 189400 KB Output is correct
14 Correct 98 ms 189788 KB Output is correct
15 Correct 105 ms 189784 KB Output is correct
16 Correct 101 ms 189604 KB Output is correct
17 Correct 92 ms 189164 KB Output is correct
18 Correct 94 ms 189548 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 321 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 404 ms 219888 KB Output is correct
2 Correct 323 ms 222864 KB Output is correct
3 Correct 324 ms 223784 KB Output is correct
4 Correct 328 ms 222020 KB Output is correct
5 Correct 340 ms 221732 KB Output is correct
6 Correct 291 ms 226092 KB Output is correct
7 Correct 326 ms 226184 KB Output is correct
8 Correct 282 ms 217668 KB Output is correct
9 Correct 146 ms 193632 KB Output is correct
10 Correct 280 ms 217768 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 188172 KB Output is correct
2 Correct 96 ms 188088 KB Output is correct
3 Correct 90 ms 188172 KB Output is correct
4 Correct 96 ms 188132 KB Output is correct
5 Correct 87 ms 188204 KB Output is correct
6 Correct 90 ms 188248 KB Output is correct
7 Correct 86 ms 188236 KB Output is correct
8 Correct 88 ms 188204 KB Output is correct
9 Correct 91 ms 188180 KB Output is correct
10 Correct 85 ms 188212 KB Output is correct
11 Correct 91 ms 188760 KB Output is correct
12 Correct 95 ms 189364 KB Output is correct
13 Correct 96 ms 189400 KB Output is correct
14 Correct 98 ms 189788 KB Output is correct
15 Correct 105 ms 189784 KB Output is correct
16 Correct 101 ms 189604 KB Output is correct
17 Correct 92 ms 189164 KB Output is correct
18 Correct 94 ms 189548 KB Output is correct
19 Correct 744 ms 259192 KB Output is correct
20 Correct 808 ms 259168 KB Output is correct
21 Correct 675 ms 262144 KB Output is correct
22 Correct 660 ms 262144 KB Output is correct
23 Correct 661 ms 262144 KB Output is correct
24 Correct 621 ms 262144 KB Output is correct
25 Correct 562 ms 262144 KB Output is correct
26 Correct 692 ms 262144 KB Output is correct
27 Correct 681 ms 262144 KB Output is correct
28 Correct 686 ms 261972 KB Output is correct
29 Correct 677 ms 259476 KB Output is correct
30 Correct 679 ms 259412 KB Output is correct
31 Correct 663 ms 260272 KB Output is correct
32 Correct 743 ms 260264 KB Output is correct
33 Correct 739 ms 260348 KB Output is correct
34 Runtime error 415 ms 262144 KB Execution killed with signal 9
35 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 188172 KB Output is correct
2 Correct 96 ms 188088 KB Output is correct
3 Correct 90 ms 188172 KB Output is correct
4 Correct 96 ms 188132 KB Output is correct
5 Correct 87 ms 188204 KB Output is correct
6 Correct 90 ms 188248 KB Output is correct
7 Correct 86 ms 188236 KB Output is correct
8 Correct 88 ms 188204 KB Output is correct
9 Correct 91 ms 188180 KB Output is correct
10 Correct 85 ms 188212 KB Output is correct
11 Correct 91 ms 188760 KB Output is correct
12 Correct 95 ms 189364 KB Output is correct
13 Correct 96 ms 189400 KB Output is correct
14 Correct 98 ms 189788 KB Output is correct
15 Correct 105 ms 189784 KB Output is correct
16 Correct 101 ms 189604 KB Output is correct
17 Correct 92 ms 189164 KB Output is correct
18 Correct 94 ms 189548 KB Output is correct
19 Runtime error 321 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -