#include "bits/stdc++.h"
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
const int N = 1e6 + 10;
const int INF = 1e9 + 7;
int l[N];
int st[4 * N];
bool ans[N];
void update(int index, int l, int r, int val, int pos)
{
if(l > r || l > pos || r < pos) return;
if(l == r) { st[index] = val; return; }
int mid = (l + r) / 2;
update(index * 2, l, mid, val, pos); update(index * 2 + 1, mid + 1, r, val, pos);
st[index] = max(st[index * 2], st[index * 2 + 1]);
}
int get(int index, int l, int r, int L, int R)
{
if(l > r || l > R || r < L) return 0;
if(l >= L && r <= R) return st[index];
int mid = (l + r) / 2;
return max(get(index * 2, l, mid, L, R), get(index * 2 + 1, mid + 1, r, L, R));
}
struct upit { int l, r, k, pos; };
upit make_upit(int p)
{
upit a; cin >> a.l >> a.r >> a.k;
a.pos = p;
return a;
}
bool comp(upit a, upit b)
{
return (a.r < b.r || (a.r == b.r && (a.l < b.l)));
}
int main()
{
FAST;
int n, q; cin >> n >> q;
vector < int > v(n + 1);
for(int i = 1; i <= n; i++) cin >> v[i];
v[0] = INF;
stack < int > st; st.push(0);
for(int i = 1; i <= n; i++)
{
while(v[st.top()] <= v[i]) st.pop();
l[i] = st.top();
st.push(i);
}
// for(int i = 1; i <= n; i++) cout << l[i] << " ";
// cout << "\n";
vector < upit > t(q);
for(int i = 0; i < q; i++) t[i] = make_upit(i + 1);
sort(begin(t), end(t), comp);
int j = 1;
for(auto it : t)
{
while(j <= it.r) { update(1, 1, n, v[j] + v[l[j]], l[j]); j++; }
ans[it.pos] = (get(1, 1, n, it.l, it.r) <= it.k);
}
for(int i = 1; i <= q; 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... |