Submission #572107

#	Time	Username	Problem	Language	Result	Execution time	Memory
572107		vovamr	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	34 / 100	808 ms	262144 KiB

sortbooks

#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 (stderr)

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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 13
• Subtask 4: 17 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23