#include "bits/stdc++.h"
#define mxN 1000006
using namespace std;
struct stree{
int ar[4 * mxN];
void upd(int i, int x, int l, int r, int v){
if (l < r){
int mi = (l + r) / 2;
if (i <= mi)
upd(i, x, l, mi, v * 2);
else
upd(i, x, mi + 1, r, v * 2 + 1);
ar[v] = max(ar[v * 2], ar[v * 2 + 1]);
} else ar[v] = x;
}
int qry(int a, int b, int l, int r, int v){
if (a <= l && r <= b)
return ar[v];
else if (a <= r && l <= b){
int mi = (l + r) / 2;
int ans = 0;
int lr = qry(a, b, l, mi, v * 2);
int rr = qry(a, b, mi + 1, r, v * 2 + 1);
return max(lr, rr);
} else return 0;
}
} st;
int ans[mxN];
int w[mxN];
int main(){
int N, M;
cin >> N >> M;
for (int i = 1; i <= N; i ++)
cin >> w[i];
vector<tuple<int,int,int,int>> qrys;
for (int i = 1; i <= M; i ++){
int L, R, K;
cin >> L >> R >> K;
qrys.emplace_back(R, L, K, i);
}
sort(begin(qrys), end(qrys));
stack<int> stk;
int ls = 0;
for (int i = 0; i < M; i ++){
auto& [R, L, K, I] = qrys[i];
if (ls < R){
for (int j = ls + 1; j <= R; j ++){
while (stk.size() && w[stk.top()] < w[j]){
stk.pop();
}
if (stk.size()){
int v = stk.top();
st.upd(v, w[v] + w[j], 1, N, 1);
}
stk.push(j);
}
ls = R;
}
int loc = st.qry(L, R, 1, N, 1);
ans[I] = loc <= K;
}
for (int i = 1; i <= M; i ++)
cout << ans[i] << endl;
}
# | 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... |