Submission #167839

#TimeUsernameProblemLanguageResultExecution timeMemory
167839beso123Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
0 / 100
3015 ms59024 KiB
#include<bits/stdc++.h> #define int long long using namespace std; const int N=(1e6)+10; int n,m,a[N],t[4*N],t1[4*N]; void UPD(int v,int i,int j,int pos,int val){ if(i==j && pos==i){ t[v]+=val; return; } int mid=(i+j)/2; if(pos<=mid) UPD(v*2,i,mid,pos,val); else UPD(v*2+1,mid+1,j,pos,val); t[v]=max(t[v*2],t[v*2+1]); } int GET(int v,int i,int j,int l,int r){ if(l>r) return 0; if(i==l && j==r) return t[v]; int mid=(i+j)/2; int g1=GET(v*2,i,mid,l,min(r,mid)); int g2=GET(v*2+1,mid+1,j,max(l,mid+1),r); return max(g1,g2); } void build(int v,int i,int j){ if(i==j){ t1[v]=a[i]; return; } int mid=(i+j)/2; build(v*2,i,mid); build(v*2+1,mid+1,j); t1[v]=min(t1[v*2],t1[v*2+1]); } int GET_min(int v,int i,int j,int l,int r){ if(l>r) return INT_MAX; if(i==l && j==r) return t1[v]; int mid=(i+j)/2; int g1=GET_min(v*2,i,mid,l,min(r,mid)); int g2=GET_min(v*2+1,mid+1,j,max(l,mid+1),r); return min(g1,g2); } main(){ cin>>n>>m; for(int k=1;k<=n;k++){ cin>>a[k]; } build(1,1,n); if(a[1]>a[2]) UPD(1,1,n,1,a[1]); if(a[n]<a[n-1]) UPD(1,1,n,n,a[n]); for(int k=2;k<n;k++){ if(a[k-1]<a[k] && a[k]<a[k+1]) continue; UPD(1,1,n,k,a[k]); } for(int k=1;k<=m;k++){ int l,r,c; cin>>l>>r>>c; int mn=GET_min(1,1,n,l,r); if(a[l]<a[l+1]) l++; if(a[r]>a[r-1]) r--; int pas=GET(1,1,n,l,r); if(mn+pas>c) cout<<0<<endl; else cout<<1<<endl; } return 0; }

Compilation message (stderr)

sortbooks.cpp:48:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...