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 N = 1e6 + 5;
vector<int> st[4*N];
int mx[4*N], n;
void build(vector<int> &a, int i = 1, int l2 = 1, int r2 = n) {
if (l2 == r2) {
st[i]= {a[l2]};
mx[i] = 0;
return;
}
int m2 = (l2 + r2)/2;
build(a, 2*i, l2, m2);
build(a, 2*i+1, m2+1, r2);
st[i].resize(r2 - l2 + 1);
merge(st[2*i].begin(), st[2*i].end(), st[2*i+1].begin(), st[2*i+1].end(), st[i].begin());
int id = upper_bound(st[2*i+1].begin(), st[2*i+1].end(), st[2*i].back()) - st[2*i+1].begin();
if (!id) mx[i] = max(mx[2*i], mx[2*i+1]);
else {
mx[i] = max({mx[2*i], mx[2*i+1], st[2*i].back() + st[2*i+1][id-1]});
}
}
int M = 0, MS = 0;
void qry(int l, int r, int i = 1, int l2 = 1, int r2 = n) {
if (l <= l2 && r2 <= r) {
int id = upper_bound(st[i].begin(), st[i].end(), M) - st[i].begin();
MS = max(MS, mx[i]);
if (id) MS = max({MS, M + st[i][id-1]});
M = max(M, st[i].back());
return;
}
int m2 = (l2 + r2)/2;
if (l <= m2) qry(l, r, 2*i, l2, m2);
if (m2 +1 <= r) qry(l, r, 2*i+1, m2+1, r2);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int m;
cin >> n >> m;
vector<int> a(n+1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
build(a);
while (m--) {
int l, r, k;
cin >> l >> r >> k;
M = 0, MS = 0;
qry(l, r);
cout << (MS <= k) << '\n';
}
}
# | 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... |