// Muallif: Mansuraliyev Husanboy Murotali o'g'li >> NamPS
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const double PI=3.1415926535897932384626433832795;
// 0-9 >> 48-57; A-Z>>65-90 and a-z>>97-122 respectively;
const int N=1e6+1;
ll tree[N*2], a[N]; map<int,ll> mp;
int n;
void build(int x,int l, int r){
if(l==r){
tree[x]=a[l];return;
}
int m=(l+r)/2;
build(x*2,l,m); build(x*2+1,m+1,r);
tree[x]=max(tree[x*2],tree[x*2+1]);return;
}
ll get(int x, int l, int r, int ll, int rr){
if(ll>r||rr<l){
return 0;
}
if(l>=ll&&r<=rr){
return tree[x];
}
if(l>rr||r<ll){
return 1000000001;
}
int m=(l+r)/2;
return max(get(x*2,l,m,ll,rr),get(x*2+1,m+1,r,ll,rr));
}
void solve(){
int l,r;ll k; cin>>l>>r>>k;
while(l<r){
ll ans=get(1,1,n,l,r);//cout<<get(1,1,n,l,r)<<"gh ";
if(mp[ans]!=r){
if(get(1,1,n,mp[ans]+1,r)+ans>k){
cout<<"0\n"; //cout<<get(1,1,n,mp[ans]+1,r)<<"ld ";
return ;
}
}r--;
}
cout<<"1\n";
}
int main(){
int m; cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]=i;
build(1,1,n);
/*for(int i=1;i<=2*n;i++){
cout<<i<<": "<<tree[i]<<"\n";
}*/
while(m--){
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
304 KB |
Output is correct |
| 5 |
Correct |
1 ms |
300 KB |
Output is correct |
| 6 |
Correct |
2 ms |
304 KB |
Output is correct |
| 7 |
Correct |
2 ms |
332 KB |
Output is correct |
| 8 |
Correct |
20 ms |
312 KB |
Output is correct |
| 9 |
Correct |
6 ms |
332 KB |
Output is correct |
| 10 |
Incorrect |
6 ms |
332 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
304 KB |
Output is correct |
| 5 |
Correct |
1 ms |
300 KB |
Output is correct |
| 6 |
Correct |
2 ms |
304 KB |
Output is correct |
| 7 |
Correct |
2 ms |
332 KB |
Output is correct |
| 8 |
Correct |
20 ms |
312 KB |
Output is correct |
| 9 |
Correct |
6 ms |
332 KB |
Output is correct |
| 10 |
Incorrect |
6 ms |
332 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1247 ms |
173512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3068 ms |
3200 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
304 KB |
Output is correct |
| 5 |
Correct |
1 ms |
300 KB |
Output is correct |
| 6 |
Correct |
2 ms |
304 KB |
Output is correct |
| 7 |
Correct |
2 ms |
332 KB |
Output is correct |
| 8 |
Correct |
20 ms |
312 KB |
Output is correct |
| 9 |
Correct |
6 ms |
332 KB |
Output is correct |
| 10 |
Incorrect |
6 ms |
332 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
304 KB |
Output is correct |
| 5 |
Correct |
1 ms |
300 KB |
Output is correct |
| 6 |
Correct |
2 ms |
304 KB |
Output is correct |
| 7 |
Correct |
2 ms |
332 KB |
Output is correct |
| 8 |
Correct |
20 ms |
312 KB |
Output is correct |
| 9 |
Correct |
6 ms |
332 KB |
Output is correct |
| 10 |
Incorrect |
6 ms |
332 KB |
Output isn't correct |
