#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
const int mxn = 1e6+10;
int arr[mxn];
int N,Q;
struct SEG{
#define mid ((l+r)>>1)
#define ls now*2+1
#define rs now*2+2
struct node{
int mx,mn;
int val;
node(){mx = 0,mn = 0,val = 0;}
};
node seg[mxn*4];
SEG(){
for(auto &i:seg)i = node();
}
node pull(node a,node b){
node re;
re.mx = max(a.mx,b.mx);
re.mn = min(a.mn,b.mn);
re.val = max({a.val,b.val,a.mx-b.mn});
return re;
}
void build(int now,int l,int r){
if(l == r){
seg[now].mx = seg[now].mn = arr[l];
seg[now].val = 0;
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
seg[now] = pull(seg[ls],seg[rs]);
return;
}
node getval(int now,int l,int r,int s,int e){
if(l>=s&&e>=r)return seg[now];
if(mid>=e)return getval(ls,l,mid,s,e);
else if(mid<s)return getval(rs,mid+1,r,s,e);
else return pull(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
}
#undef ls
#undef rs
#undef mid
};
SEG seg;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N>>Q;
for(int i = 1;i<=N;i++)cin>>arr[i];
seg.build(0,1,N);
while(Q--){
int s,e,v;
cin>>s>>e>>v;
int re = seg.getval(0,1,N,s,e).val;
cout<<(re<=v)<<'\n';
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
47708 KB |
Output is correct |
2 |
Correct |
15 ms |
47708 KB |
Output is correct |
3 |
Incorrect |
15 ms |
47708 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
47708 KB |
Output is correct |
2 |
Correct |
15 ms |
47708 KB |
Output is correct |
3 |
Incorrect |
15 ms |
47708 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
879 ms |
53132 KB |
Output is correct |
2 |
Incorrect |
866 ms |
53496 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
69 ms |
47956 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
47708 KB |
Output is correct |
2 |
Correct |
15 ms |
47708 KB |
Output is correct |
3 |
Incorrect |
15 ms |
47708 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
47708 KB |
Output is correct |
2 |
Correct |
15 ms |
47708 KB |
Output is correct |
3 |
Incorrect |
15 ms |
47708 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |