Submission #992784

#TimeUsernameProblemLanguageResultExecution timeMemory
992784simona1230Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
13 / 100
1344 ms16064 KiB
#include <bits/stdc++.h> using namespace std; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } long long n,m,a[1000001]; void read() { cin>>n>>m; for(long long i=1;i<=n;i++) cin>>a[i]; } long long maxx[1000001][32]; long long minn[1000001][32]; long long pw[1000001]; void prec() { long long x=1,y=0; while(x<=n) { pw[x]=y; cout<<x<<" "<<pw[x]<<endl; if(x+1==(1<<(y+1))) y++; x++; } for(long long i=1;i<=n;i++) maxx[i][0]=minn[i][0]=a[i]; for(long long j=1;j<20;j++) { for(long long i=1;i<=n;i++) { minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]); maxx[i][j]=max(maxx[i][j-1],maxx[i+(1<<(j-1))][j-1]); } } } long long max_(long long l,long long r) { long long len=r-l+1; return max(maxx[l][pw[len]],maxx[r-(1<<(pw[len]))+1][pw[len]]); } long long min_(long long l,long long r) { long long len=r-l+1; return min(minn[l][pw[len]],minn[r-(1<<(pw[len]))+1][pw[len]]); } void solve() { for(long long i=1;i<=m;i++) { long long l,r,k; cin>>l>>r>>k; long long ans=0; for(long long j=l;j<r;j++) { //cout<<l<<" "<<j<<" "<<max_(l,j)<<" "<<j+1<<" "<<r<<" "<<min_(j+1,r)<<endl; ans=max(ans,max_(l,j)-min_(j+1,r)); } if(ans<=k)cout<<1<<endl; else cout<<0<<endl; } } void subt3() { vector<long long> v; for(long long i=2;i<=n;i++) { if(a[i]<a[i-1])v.push_back(i); } for(long long i=1;i<=m;i++) { long long l,r,k; cin>>l>>r>>k; if(v.size()==0) { cout<<1<<endl; continue; } if(v[v.size()-1]<=l||v[0]>r) { cout<<0<<endl; continue; } long long lf=0,rt=v.size()-1; bool f=0; while(lf<=rt) { long long mid=(lf+rt)/2; if(v[mid]<=l) { lf=mid+1; } else if(v[mid]>r) { rt=mid-1; } else { f=1; break; } } if(f)cout<<0<<endl; else cout<<1<<endl; } } int main() { speed(); read(); if(0&&n<=5000&&m<=5000) { prec(); solve(); return 0; } subt3(); return 0; }
#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...