#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define sp << " " <<
#define endl << '\n'
vector<long long int> lst, cvp;
long long int N, Q;
class segtree{
private:
vector<long long int> tre;
void _set(long long int ind, long long int x, long long int l, long long int r, long long int s){
if (ind < l || r < ind)
return;
tre[s] = max(tre[s], x);
if (l == r)
return;
long long int m = (l + r) >> 1;
_set(ind, x, l, m, s << 1);
_set(ind, x, m + 1, r, (s << 1) | 1);
}
long long int _get(long long int ind, long long int l, long long int r, long long int s){
if (r < ind)
return LONG_LONG_MIN;
if (ind <= l)
return tre[s];
long long int m = (l + r) >> 1;
return max(_get(ind, l, m, s << 1), _get(ind, m + 1, r, (s << 1) | 1));
}
public:
segtree(){
tre.resize(N * 4);
}
void set(long long int ind, long long int x){
_set(ind, x, 0, N, 1);
}
long long int get(long long int L){
return _get(L, 0, N, 1);
}
};
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> Q;
lst.resize(N);
for (int i = 0; i < N; i++)
cin >> lst[i];
vector<array<long long int, 4>> q;
q.reserve(Q);
cvp.resize(Q, 1);
for (int i = 0; i < Q; i++){
long long int a, b, w;
cin >> a >> b >> w;
a--; b--;
if (a != b)
q.push_back({a, b, w, i});
}
sort(all(q), [](const array<long long int, 4> a, const array<long long int, 4> b) -> bool{ return a[1] < b[1]; });
segtree tree = segtree();
stack<pair<long long int, long long int>> stc;
long long int r = 0;
for (auto quest : q){
while (r <= quest[1]){
while (stc.size() && stc.top().first < lst[r]){
stc.pop();
}
if (stc.size())
tree.set(stc.top().second, stc.top().first + lst[r]);
stc.push({ lst[r], r });
r++;
}
cvp[quest[3]] = tree.get(quest[0]) <= quest[2];
}
for (int i = 0; i < Q; i++){
cout << cvp[i] endl;
}
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... |