#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
int treeMax[800005],treeMin[800005],red[200005],MIN,MAX;
void build_tree(int l,int r,int now){
if(l==r){
treeMax[now]=red[l];
treeMin[now]=red[l];
return ;
}
int mid=(l+r)/2;
build_tree(l,mid,now*2+1);
build_tree(mid+1,r,now*2+2);
treeMax[now]=max(treeMax[now*2+1],treeMax[now*2+2]);
treeMin[now]=min(treeMin[now*2+1],treeMin[now*2+2]);
//cout<<treeMax[now]<<"-"<<treeMin[now]<<endl;
return ;
}
void find_tree(int l,int r,int L,int R,int now){
if(l>=L && r<=R){
//cout<<treeMax[now]<<l<<" "<<r<<endl;
MAX=max(MAX,treeMax[now]);
MIN=min(MIN,treeMin[now]);
return ;
}
if(r<L || l>R){
return ;
}
int mid=(l+r)/2;
find_tree(l,mid,L,R,now*2+1);
find_tree(mid+1,r,L,R,now*2+2);
}
int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)cin>>red[i];
build_tree(0,n-1,0);
for(int i=0;i<m;i++){
int l,r,k;
cin>>l>>r>>k;
l--;r--;
MIN=10000000;
MAX=-1;
find_tree(0,n-1,l,r,0);
//cout<<MIN<<MAX<<endl;
if(MAX+MIN<=k)cout<<1<<endl;
else cout<<0<<endl;
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
94 ms |
8408 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
66 ms |
2940 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |