oj.uz

Submission #572118

# Submission time Handle Problem Language Result Execution time Memory
572118 2022-06-03T17:02:21 Z vovamr Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
8 / 100
 3000 ms 51400 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 + 10;
int a[N], f[N];
inline void upd(int i, int x) { i += 2; for (; i < N; ++i) chmax(f[i], x); }
inline int get(int i) { i += 2; int ans = 0; for (; i; i -= i & -i) { chmax(ans, f[i]); } return ans; }

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

	ve<int> stk{0};
	ve<int> le(n, -1), re(n, -1);
	for (int i = 1; i < n; ++i) {
		while (sz(stk) && a[stk.back()] <= a[i]) stk.pop_back();
		if (sz(stk)) le[i] = stk.back();
		stk.pb(i);
	}
	stk = {n - 1};
	for (int i = n - 2; ~i; --i) {
		while (sz(stk) && a[stk.back()] >= a[i]) stk.pop_back();
		if (sz(stk)) re[i] = stk.back();
		stk.pb(i);
	}

	ve<array<int,3>> vls;
	vls.reserve(2 * n);

	for (int i = 0; i < n; ++i) {
		if (~le[i]) vls.pb({le[i], i, a[i] + a[le[i]]});
		if (~re[i]) vls.pb({i, re[i], a[i] + a[re[i]]});
	}
	
	ve<int> prv(q);
	ve<array<int,3>> qu(q);
	for (int i = 0; i < q; ++i) {
		int l, r, k;
		cin >> l >> r >> k;
		qu[i] = {--l, --r, i}, prv[i] = k;
	}

	sort(all(qu));
	sort(all(vls));

	int p = sz(vls) - 1;
	for (int i = sz(qu) - 1; ~i; --i) {
		auto &[l, r, id] = qu[i];
		while (~p && vls[p][0] >= l) { upd(vls[p][1], vls[p][2]); --p; }
		prv[id] -= get(r);
	}

	for (int i = 0; i < q; ++i) cout << (prv[i] >= 0 ? 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;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4180 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 183 ms 4240 KB Output is correct
4 Correct 76 ms 4228 KB Output is correct
5 Correct 240 ms 4180 KB Output is correct
6 Correct 653 ms 4252 KB Output is correct
7 Correct 661 ms 4256 KB Output is correct
8 Correct 229 ms 4180 KB Output is correct
9 Correct 134 ms 4240 KB Output is correct
10 Correct 294 ms 4244 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4180 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 183 ms 4240 KB Output is correct
4 Correct 76 ms 4228 KB Output is correct
5 Correct 240 ms 4180 KB Output is correct
6 Correct 653 ms 4252 KB Output is correct
7 Correct 661 ms 4256 KB Output is correct
8 Correct 229 ms 4180 KB Output is correct
9 Correct 134 ms 4240 KB Output is correct
10 Correct 294 ms 4244 KB Output is correct
11 Correct 1910 ms 4336 KB Output is correct
12 Execution timed out 3083 ms 4436 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4180 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 183 ms 4240 KB Output is correct
4 Correct 76 ms 4228 KB Output is correct
5 Correct 240 ms 4180 KB Output is correct
6 Correct 653 ms 4252 KB Output is correct
7 Correct 661 ms 4256 KB Output is correct
8 Correct 229 ms 4180 KB Output is correct
9 Correct 134 ms 4240 KB Output is correct
10 Correct 294 ms 4244 KB Output is correct
11 Correct 1910 ms 4336 KB Output is correct
12 Execution timed out 3083 ms 4436 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4180 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 183 ms 4240 KB Output is correct
4 Correct 76 ms 4228 KB Output is correct
5 Correct 240 ms 4180 KB Output is correct
6 Correct 653 ms 4252 KB Output is correct
7 Correct 661 ms 4256 KB Output is correct
8 Correct 229 ms 4180 KB Output is correct
9 Correct 134 ms 4240 KB Output is correct
10 Correct 294 ms 4244 KB Output is correct
11 Correct 1910 ms 4336 KB Output is correct
12 Execution timed out 3083 ms 4436 KB Time limit exceeded
13 Halted 0 ms 0 KB -