#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,l,r,ans,N=1024*1024;
int mas[1000001],par[1000001],val[1000001],hey[3000001],tree[3000001];
pair <int,int> p[1000001][20];
vector <int> v[1000001];
void dfs(int u) {
int i;
p[u][0]={par[u],val[u]};
for (i=1;i<20;i++)
if (p[p[u][i-1].first][i-1].first)
p[u][i]={p[p[u][i-1].first][i-1].first,max(p[u][i-1].second,p[p[u][i-1].first][i-1].second)};
for (i=0;i<(v[u].size());i++)
dfs(v[u][i]);
}
int solve(int x,int y,int p,int l,int r) {
if (l>y || x>r)
return 0;
if (l>=x && r<=y)
return tree[p];
return max(solve(x,y,2*p,l,(l+r)/2),solve(x,y,2*p+1,(l+r)/2+1,r));
}
void build_tree(int p) {
if (p>=N) {
if ((p-N+1)<=n)
tree[p]=mas[p-N+1];
return;
}
build_tree(2*p);
build_tree(2*p+1);
tree[p]=max(tree[2*p],tree[2*p+1]);
}
int main() {
cin>>n>>m;
for (i=1;i<=n;i++)
scanf("%d",&(mas[i]));
build_tree(1);
for (i=n;i>0;i--) {
for (;r>0;r--)
if (mas[hey[r]]>=mas[i])
break;
par[i]=hey[r];
v[hey[r]].push_back(i);
hey[++r]=i;
}
for (i=1;i<=n;i++)
if (par[i]>(i+1))
val[i]=mas[i]+solve(i+1+N-1,par[i]-1+N-1,1,N,2*N-1);
for (i=0;i<(v[0].size());i++)
dfs(v[0][i]);
for (mas[0]=1;mas[0]<=m;mas[0]++) {
scanf("%d %d %d",&l,&r,&j);
if (l==r) {
printf("1\n")
continue;
}
ans=0;
for (i=19;i>=0;i--)
if (p[l][i].first && p[l][i].first<=r) {
ans=max(ans,p[l][i].second);
l=p[l][i].first;
}
if (r>l)
ans=max(ans,mas[l]+solve(l+1+N-1,r+N-1,1,N,2*N-1));
if (ans>j)
printf("0\n");
else
printf("1\n");
}
}
Compilation message
sortbooks.cpp: In function 'void dfs(int)':
sortbooks.cpp:13:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<(v[u].size());i++)
~^~~~~~~~~~~~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<(v[0].size());i++)
~^~~~~~~~~~~~~~
sortbooks.cpp:55:13: error: expected ';' before 'continue'
continue;
^~~~~~~~
sortbooks.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&(mas[i]));
~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&l,&r,&j);
~~~~~^~~~~~~~~~~~~~~~~~~~~
