#include<bits/stdc++.h>
using namespace std;
const int M = 2 << 20, N = (1 << 20), inf = 1e9;
struct node {
vector<int> vec;
int mi;
} seg[M];
int n, m, a[N];
void build(int s = 0, int e = n, int v = 1)
{
if(e - s == 1)
{
seg[v].mi = 0;
seg[v].vec = {a[s]};
return;
}
int mid = (s + e) / 2, lc = 2 * v ,rc = lc + 1;
build(s, mid, lc);
build(mid, e, rc);
seg[v].mi = max(seg[lc].mi, seg[rc].mi);
vector<int> &l = seg[lc].vec;
vector<int> &r = seg[rc].vec;
int i = 0, j = 0;
while(i < l.size() || j < r.size())
{
if(i == l.size() || (j < r.size() && l[i] >= r[j]))
{
seg[v].vec.push_back(r[j]), j++;
if(l.size()) seg[v].mi = max(seg[v].mi, r[j] + l[i]);
}
else
seg[v].vec.push_back(l[i]), i++;
}
}
int x;
int get(int l, int r, int s = 0, int e = n, int v = 1)
{
if(r <= s || e <= l) return 0;
if(l <= s && e <= r)
{
int ans = seg[v].mi;
auto it = lower_bound(seg[v].vec.begin(), seg[v].vec.end(), x);
if(it != seg[v].vec.begin())
{
it--;
ans = max(ans, x + *it);
}
x = max(x, seg[v].vec.back());
return ans;
}
int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
int ans = get(l, r, s, mid, lc);
ans = max(ans, get(l, r, mid, e, rc));
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 0; i < n; i ++)
cin >> a[i];
build();
while(m--)
{
int l, r, k;
cin >> l >> r >> k;
l--;
x = -inf;
int res = get(l, r);
cout << (res <= k) << '\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... |