Submission #1113492

#TimeUsernameProblemLanguageResultExecution timeMemory
1113492I_FloPPed21Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
0 / 100
1551 ms162484 KiB
#include <iostream> #include <vector> #include <stack> using namespace std; int n,q; const int N=1e6+5; long long v[N]; long long sum[4*N],lazy[4*N],seg[4*N],adaug[4*N],best[4*N],right_bound[N]; struct hedgehog { long long i,r,k; }; vector<hedgehog>query[N]; void find_bound() { stack<long long>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]==0) 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]=0; } void update(int nod,int st,int dr,int l,int r,long long 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]; } 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]); } } int answer(int nod,int st,int dr,int l,int r) { if(st>dr) return 0; 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++) { long long l,r,k; cin>>l>>r>>k; query[l].push_back({i,r,k}); } } bool afis[N]; void rezolva() { for(int i=n; i>=1; i--) { int dr=right_bound[i]-1; if(i+1<=dr) update(1,1,n,i+1,dr,v[i]); for (auto [x,y,z]:query[i]) { afis[x]=(answer(1,1,n,i+1,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; }
#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...