#include <bits/stdc++.h>
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout)
const int N=1e6+1;
const int inf=1e18;
const int mod=1e9+7;
using namespace std;
int n;
struct edge{
int mn,mx,ps;
};
vector<int>v;
edge t[4*N];
void build(int n,int tl,int tr){
if(tl==tr){
t[n].mx=v[tl];
t[n].mn=v[tl];
t[n].ps=tl;
return;
}
int mid=(tl+tr)/2;
build(n*2,tl,mid);
build(n*2+1,mid+1,tr);
t[n].mn=min(t[n*2].mn,t[n*2+1].mn);
t[n].mx=max(t[n*2].mx,t[n*2+1].mx);
if(t[n].mx==t[n*2].mx){
t[n].ps=t[n*2].ps;
}else{
t[n].ps=t[n*2+1].ps;
}
}
pair<int,int> getmx(int n,int tl,int tr,int l,int r){
if(tr<l||r<tl){
return {-1,-1};
}
if(l<=tl&&tr<=r){
return {t[n].mx,t[n].ps};
}
int mid=(tl+tr)/2;
pair<int,int> p=getmx(n*2,tl,mid,l,r);
pair<int,int> o=getmx(n*2+1,mid+1,tr,l,r);
pair<int,int> ans;
ans.first=max(p.first,o.first);
if(ans.first==p.first){
ans.second=p.second;
}else{
ans.second=o.second;
}
return ans;
}
int getmn(int n,int tl,int tr,int l,int r){
if(tr<l||r<tl){
return inf;
}
if(l<=tl&&tr<=r){
return t[n].mn;
}
int mid=(tl+tr)/2;
return min(getmn(n*2,tl,mid,l,r),getmn(n*2+1,mid+1,tr,l,r));
}
signed main(){
boost;
int n,m;
cin>>n>>m;
v.push_back(0);
for(int i=1;i<=n;i++){
int x;
cin>>x;
v.push_back(x);
}
while(m--){
int l,r,k;
cin>>l>>r>>k;
int mx=0;
int mn=inf;
int ok=0;
for(int i=l;i<=r;i++){
if(i!=l){
if(v[i]<v[i-1]){
ok=1;
}
}
mx=max(mx,v[i]);
mn=min(mn,v[i]);
}
for(int i=r;i>=l;i--){
mx=max(mx,v[i]);
if(mx==v[i]){
mx=0;
continue;
}
mx=max(mx,v[i]);
}
if(mx+mn<=k||ok==0){
cout<<1<<"\n";
}else{
cout<<0<<"\n";
}
}
}
Compilation message
sortbooks.cpp:5:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
5 | const int inf=1e18;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3035 ms |
12048 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3050 ms |
2948 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
