Submission #1113465

#TimeUsernameProblemLanguageResultExecution timeMemory
1113465I_FloPPed21Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
0 / 100
1365 ms140264 KiB
#include <iostream> #include <vector> #include <stack> using namespace std; int n,q; const int N=1e6+5; int v[N]; int sum[4*N],lazy[4*N],seg[4*N],adaug[4*N],best[4*N],right_bound[N]; struct hedgehog { int i,r,k; }; vector<hedgehog>query[N]; void find_bound() { stack<int>st; for(int i=1;i<=n;i++) { while(!st.empty()&&v[st.top()]<v[i]) { right_bound[st.top()]=i; st.pop(); } st.push(i); } while(!st.empty()) { right_bound[st.top()]=n+1; st.pop(); } } void propaga(int nod) { if(lazy[nod]==-1) return; adaug[nod*2]=lazy[nod]; adaug[nod*2+1]=lazy[nod]; lazy[nod*2]=lazy[nod]; lazy[nod*2+1]=lazy[nod]; best[nod*2]=(seg[nod*2]+lazy[nod]); best[nod*2+1]=(seg[nod*2+1]+lazy[nod]); lazy[nod]=-1; } void update(int nod,int st,int dr,int l,int r,int val) { sum[nod]=seg[nod]+adaug[nod]; if(l<=st&&dr<=r) { lazy[nod]=val; adaug[nod]=val; sum[nod]=seg[nod]+adaug[nod]; best[nod]=sum[nod]; } else if(l>dr||st>r) return; else { int mij=(st+dr)/2; propaga(nod); update(nod*2,st,mij,l,r,val); update(nod*2+1,mij+1,dr,l,r,val); best[nod]=max(best[nod*2],best[nod*2+1]); } } void build(int nod,int st,int dr) { if(st==dr) {seg[nod]=v[st]; best[nod]=seg[nod];} else { int mij=(st+dr)/2; build(nod*2,st,mij); build(nod*2+1,mij+1,dr); seg[nod]=max(seg[nod*2],seg[nod*2+1]); best[nod]=max(best[nod*2],best[nod*2+1]); } } int answer(int nod,int st,int dr,int l,int r) { if(l<=st&&dr<=r) { return best[nod]; } else if(l>dr||st>r) return -1; else { propaga(nod); int mij=(st+dr)/2; return max(answer(nod*2,st,mij,l,r),answer(nod*2+1,mij+1,dr,l,r)); } } void citeste() { cin>>n>>q; for(int i=1;i<=n;i++) cin>>v[i]; for(int i=1;i<=q;i++) { int l,r,k; cin>>l>>r>>k; query[l].push_back({i,r,k}); } } int afis[N]; void rezolva() { for(int i=n;i>=1;i--) { int dr=right_bound[i]-1; update(1,1,n,i+1,dr,v[i]); for (auto [x,y,z]:query[i]) { afis[x]=(answer(1,1,n,i,y)<=z); } } for(int i=1;i<=q;i++) cout<<afis[i]<<'\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); citeste(); build(1,1,n); find_bound(); rezolva(); return 0; }

Compilation message (stderr)

sortbooks.cpp: In function 'void rezolva()':
sortbooks.cpp:116:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  116 |         for (auto [x,y,z]:query[i])
      |                   ^
#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...