Submission #168562

#TimeUsernameProblemLanguageResultExecution timeMemory
168562beso123Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
0 / 100
3048 ms59772 KiB
#include <bits/stdc++.h> #define int long long #define pii pair<int,pair<int,pair<int,int>>> #define x first #define y second.first #define z second.second.first #define p second.second.second using namespace std; const int N=(1e6)+3; int n,q,a[N],t[4*N],gr[N],ans[N]; vector<pii> Q; stack<int> st; void UPD(int v,int i,int j,int pos,int val){ if(i==j){ 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(mid+1,l),r); return max(g1,g2); } bool comp_sort(pii a,pii b){ return a.y<b.y; } main(){ cin>>n>>q; for(int k=1;k<=n;k++) cin>>a[k]; a[0]=LONG_LONG_MAX; st.push(0); for(int k=1;k<=n;k++){ while(a[st.top()]<=a[k]){ st.pop(); } gr[k]=st.top(); st.push(k); } for(int k=1;k<=q;k++){ int a,b,c; cin>>a>>b>>c; Q.push_back({a,{b,{c,k}}}); } sort(Q.begin(),Q.end(),comp_sort); int j=0; for(int k=1;k<=n;k++){ if(gr[k]){ UPD(1,1,n,k,a[gr[k]]+a[k]); } while(Q[j].y==k){ if(GET(1,1,n,Q[j].x,Q[j].y)<=Q[j].z) ans[Q[j].p]=1; j++; } } for(int k=1;k<=q;k++) cout<<ans[k]<<endl; return 0; }

Compilation message (stderr)

sortbooks.cpp:38: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...