oj.uz

Submission #572116

# Submission time Handle Problem Language Result Execution time Memory
572116 2022-06-03T16:50:24 Z vovamr Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 79452 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;
int a[N], mx[N], ar[N];

int answer[N], hui[N];

inline void solve(int l, int r, ve<array<int,3>> &q) {
	if (l == r) return;
	int m = l + r >> 1;

	ve<array<int,3>> ql, qr;
	for (auto &qu : q) {
		auto &[r, l, id] = qu;

		if (r <= m) ql.pb(qu);
		else if (l > m) qr.pb(qu);
	}
	solve(l, m, ql), solve(m + 1, r, qr);

	mx[m + 1] = a[m + 1];
	mx[m] = a[m];
	ar[m] = ar[m + 1] = 0;

	for (int i = m + 2; i <= r; ++i) {
		mx[i] = max(a[i], mx[i - 1]);
		ar[i] = ar[i - 1];
		if (mx[i - 1] > a[i]) chmax(ar[i], a[i] + mx[i - 1]);
	}

	set<int> st; st.insert(a[m]);
	for (int i = m - 1; i >= l; --i) {
		mx[i] = max(mx[i + 1], a[i]);
		ar[i] = ar[i + 1];
		auto it = st.lower_bound(a[i]);
		if (it != st.begin()) chmax(ar[i], a[i] + *--it);
		st.insert(a[i]);
	}

	for (auto &[r, l, id] : q) {
		if (l <= m && r > m) {
			chmax(answer[id], ar[r]);
			chmax(answer[id], ar[l]);
		}
	}

	int p = 0; st.clear();
	for (int i = m + 1; i <= r; ++i) {
		st.insert(a[i]);
		while (p < sz(q) && q[p][0] < i) ++p;
		while (p < sz(q) && q[p][0] == i) {
			auto &[r, l, id] = q[p];
			if (l <= m && r > m) {
				auto it = st.lower_bound(mx[l]);
				if (it != st.begin()) chmax(answer[id], mx[l] + *--it);
			}
			++p;
		}
	}
}

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

	ve<array<int,3>> qu(q);
	for (int i = 0; i < q; ++i) {
		int l, r, k;
		cin >> l >> r >> k;
		qu[i] = {--r, --l, i};
		hui[i] = k;
	}
	sort(all(qu));
	solve(0, n - 1, qu);
	for (int i = 0; i < q; ++i) cout << (hui[i] >= answer[i] ? 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 solve(int, int, std::vector<std::array<int, 3> >&)':
sortbooks.cpp:30:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |  int m = l + r >> 1;
      |          ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 2 ms 352 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 2 ms 352 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 4 ms 468 KB Output is correct
12 Correct 9 ms 724 KB Output is correct
13 Correct 10 ms 732 KB Output is correct
14 Correct 11 ms 836 KB Output is correct
15 Correct 10 ms 724 KB Output is correct
16 Correct 8 ms 700 KB Output is correct
17 Correct 7 ms 724 KB Output is correct
18 Correct 4 ms 604 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3021 ms 79452 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 7088 KB Output is correct
2 Correct 200 ms 4992 KB Output is correct
3 Correct 94 ms 4880 KB Output is correct
4 Correct 98 ms 5640 KB Output is correct
5 Correct 86 ms 6196 KB Output is correct
6 Correct 75 ms 4940 KB Output is correct
7 Correct 78 ms 4940 KB Output is correct
8 Correct 64 ms 5356 KB Output is correct
9 Correct 49 ms 4368 KB Output is correct
10 Correct 63 ms 5344 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 2 ms 352 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 4 ms 468 KB Output is correct
12 Correct 9 ms 724 KB Output is correct
13 Correct 10 ms 732 KB Output is correct
14 Correct 11 ms 836 KB Output is correct
15 Correct 10 ms 724 KB Output is correct
16 Correct 8 ms 700 KB Output is correct
17 Correct 7 ms 724 KB Output is correct
18 Correct 4 ms 604 KB Output is correct
19 Correct 658 ms 14960 KB Output is correct
20 Correct 622 ms 14756 KB Output is correct
21 Correct 653 ms 14048 KB Output is correct
22 Correct 635 ms 13788 KB Output is correct
23 Correct 615 ms 13832 KB Output is correct
24 Correct 407 ms 14112 KB Output is correct
25 Correct 402 ms 14060 KB Output is correct
26 Correct 409 ms 14816 KB Output is correct
27 Correct 405 ms 14716 KB Output is correct
28 Correct 411 ms 12048 KB Output is correct
29 Correct 440 ms 13104 KB Output is correct
30 Correct 421 ms 13172 KB Output is correct
31 Correct 415 ms 12896 KB Output is correct
32 Correct 422 ms 12860 KB Output is correct
33 Correct 412 ms 12724 KB Output is correct
34 Correct 412 ms 17848 KB Output is correct
35 Correct 402 ms 17888 KB Output is correct
36 Correct 406 ms 17672 KB Output is correct
37 Correct 411 ms 17656 KB Output is correct
38 Correct 410 ms 17880 KB Output is correct
39 Correct 472 ms 16960 KB Output is correct
40 Correct 282 ms 14044 KB Output is correct
41 Correct 135 ms 12448 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 2 ms 352 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 4 ms 468 KB Output is correct
12 Correct 9 ms 724 KB Output is correct
13 Correct 10 ms 732 KB Output is correct
14 Correct 11 ms 836 KB Output is correct
15 Correct 10 ms 724 KB Output is correct
16 Correct 8 ms 700 KB Output is correct
17 Correct 7 ms 724 KB Output is correct
18 Correct 4 ms 604 KB Output is correct
19 Execution timed out 3021 ms 79452 KB Time limit exceeded
20 Halted 0 ms 0 KB -