oj.uz

Submission #530844

# Submission time Handle Problem Language Result Execution time Memory
530844 2022-02-27T01:25:43 Z abc864197532 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
21 / 100
 1103 ms 155972 KB 
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define pii pair<int,int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T i, U ...j) {
	cout << i << ' ', abc(j...);
}
template <typename T> void printv(T l, T r) {
	for (; l != r; ++l)
		cout << *l << " \n"[l + 1 == r];
}
#ifdef Doludu
#define test(x...) abc("[" + string(#x) + "]", x);
#define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#else
#define test(x...) void(0)
#define owo ios::sync_with_stdio(false)
#endif
const int N = 1e6 + 87;

int bit[N];

void add(int p, int v) {
	for (; p > 0; p -= p & (-p))
		bit[p] = max(bit[p], v);
}

int query(int p) {
	int ans = 0;
	for (; p < N; p += p & (-p))
		ans = max(ans, bit[p]);
	return ans;
}

vector <int> seg[N], queries[N];

int l[N], r[N], k[N];

int main () {
	owo;
	int n, q;
	cin >> n >> q;
	vector <int> a(n);
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	vector <int> stk;
	for (int i = 0; i < n; ++i) {
		while (!stk.empty() && a[stk.back()] <= a[i])
			stk.pop_back();
		if (!stk.empty()) {
			seg[i].pb(stk.back());
		}
		stk.pb(i);
	}
	stk.clear();
	for (int i = n - 1; ~i; --i) {
		while (!stk.empty() && a[stk.back()] >= a[i])
			stk.pop_back();
		if (!stk.empty()) {
			seg[stk.back()].pb(i);
		}
		stk.pb(i);
	}
	for (int i = 0; i < q; ++i)
		cin >> l[i] >> r[i] >> k[i], --l[i], --r[i], queries[r[i]].pb(i);
	vector <int> ans(n);
	for (int i = 0; i < n; ++i) {
		for (int j : seg[i]) {
			add(j + 2, a[i] + a[j]);
		}
		for (int id : queries[i]) {
			ans[id] = query(l[id] + 2);
		}
	}
	for (int i = 0; i < q; ++i)
		cout << (ans[i] <= k[i] ? 1 : 0) << '\n';
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47264 KB Output is correct
2 Correct 22 ms 47268 KB Output is correct
3 Correct 22 ms 47312 KB Output is correct
4 Correct 23 ms 47312 KB Output is correct
5 Correct 23 ms 47216 KB Output is correct
6 Correct 22 ms 47308 KB Output is correct
7 Correct 23 ms 47272 KB Output is correct
8 Correct 22 ms 47312 KB Output is correct
9 Correct 21 ms 47312 KB Output is correct
10 Correct 23 ms 47312 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47264 KB Output is correct
2 Correct 22 ms 47268 KB Output is correct
3 Correct 22 ms 47312 KB Output is correct
4 Correct 23 ms 47312 KB Output is correct
5 Correct 23 ms 47216 KB Output is correct
6 Correct 22 ms 47308 KB Output is correct
7 Correct 23 ms 47272 KB Output is correct
8 Correct 22 ms 47312 KB Output is correct
9 Correct 21 ms 47312 KB Output is correct
10 Correct 23 ms 47312 KB Output is correct
11 Runtime error 55 ms 96068 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1072 ms 154984 KB Output is correct
2 Correct 1103 ms 155940 KB Output is correct
3 Correct 1093 ms 155832 KB Output is correct
4 Correct 1101 ms 155972 KB Output is correct
5 Correct 871 ms 119680 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 56644 KB Output is correct
2 Correct 96 ms 55864 KB Output is correct
3 Correct 104 ms 52768 KB Output is correct
4 Correct 86 ms 52940 KB Output is correct
5 Correct 77 ms 53056 KB Output is correct
6 Correct 68 ms 52212 KB Output is correct
7 Correct 81 ms 52136 KB Output is correct
8 Correct 93 ms 54968 KB Output is correct
9 Runtime error 96 ms 100464 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47264 KB Output is correct
2 Correct 22 ms 47268 KB Output is correct
3 Correct 22 ms 47312 KB Output is correct
4 Correct 23 ms 47312 KB Output is correct
5 Correct 23 ms 47216 KB Output is correct
6 Correct 22 ms 47308 KB Output is correct
7 Correct 23 ms 47272 KB Output is correct
8 Correct 22 ms 47312 KB Output is correct
9 Correct 21 ms 47312 KB Output is correct
10 Correct 23 ms 47312 KB Output is correct
11 Runtime error 55 ms 96068 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47264 KB Output is correct
2 Correct 22 ms 47268 KB Output is correct
3 Correct 22 ms 47312 KB Output is correct
4 Correct 23 ms 47312 KB Output is correct
5 Correct 23 ms 47216 KB Output is correct
6 Correct 22 ms 47308 KB Output is correct
7 Correct 23 ms 47272 KB Output is correct
8 Correct 22 ms 47312 KB Output is correct
9 Correct 21 ms 47312 KB Output is correct
10 Correct 23 ms 47312 KB Output is correct
11 Runtime error 55 ms 96068 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -