This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 5;
const int MAX_M = 1e6 + 5;
const int INF = 1e9 + 7;
int w[MAX_N];
bool ans[MAX_M];
vector <tuple <int, int, int>> queries[MAX_N];
int tree[4 * MAX_N];
void update(int idx, int l, int r, int q, int v) {
if(l == r) {
tree[idx] = v;
return;
}
int mid = (l + r) / 2;
if(q <= mid) {
update(idx * 2, l, mid, q, v);
}
else {
update(idx * 2 + 1, mid + 1, r, q, v);
}
tree[idx] = max(tree[idx * 2], tree[idx * 2 + 1]);
}
int query(int idx, int l, int r, int ql, int qr) {
if(r < ql or qr < l) {
return 0;
}
if(ql <= l and r <= qr) {
return tree[idx];
}
int mid = (l + r) / 2;
return max(query(idx * 2, l, mid, ql, qr), query(idx * 2 + 1, mid + 1, r, ql, qr));
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int N, M;
cin >> N >> M;
for(int i = 1; i <= N; i++) {
cin >> w[i];
}
for(int i = 1; i <= M; i++) {
int l, r, k;
cin >> l >> r >> k;
queries[r].emplace_back(l, i, k);
}
stack <int> stk;
for(int i = 1; i <= N; i++) {
while(!stk.empty() and w[stk.top()] <= w[i]) {
stk.pop();
}
if(!stk.empty()) {
update(1, 1, N, stk.top(), w[stk.top()] + w[i]);
}
stk.push(i);
for(auto [l, id, k] : queries[i]) {
ans[id] = (query(1, 1, N, l, i) <= k);
}
}
for(int i = 1; i <= M; i++) {
cout << ans[i] << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |