Submission #1274735

#TimeUsernameProblemLanguageResultExecution timeMemory
1274735nthvnHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++20
100 / 100
1087 ms31168 KiB
#include "bits/stdc++.h" using namespace std; #define LOG(n) (63 - __builtin_clzll((n))) #define fi first #define se second #define pii pair<int,int> #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() #define pb push_back #define ll long long const int N = 1e6+5; int n,q; int a[N]; int R[N], vR[N]; struct SegTree{ struct Node{ int best, mx; void combine(Node l, Node r){ best = max(l.best, r.best); if(a[l.mx]>a[r.mx]) { best= max(best, a[l.mx]+ a[r.mx]); } else{ if(vR[l.mx]) best= max(best, a[l.mx]+ vR[l.mx]); } if(a[l.mx]> a[r.mx]) mx = l.mx; else mx = r.mx; } }tr[4*N]; void build(int id, int l, int r){ if(l==r){ tr[id].best = 0; tr[id].mx =l; return; } int mid =(l+r)>>1; build(2*id,l,mid); build(2*id+1,mid+1,r); tr[id].combine(tr[2*id],tr[2*id+1]); } Node get(int id, int l, int r, int t_l, int t_r){ if(t_l<=l&&r<=t_r) { // cerr<<l<<" "<<r<<" "<<tr[id].best<<"\n"; return tr[id]; } int mid=(l+r)>>1; if(mid>=t_l&&mid+1<=t_r) { Node ans; ans.combine(get(2*id,l,mid,t_l,t_r), get(2*id+1,mid+1,r,t_l,t_r)); return ans; } if(mid>=t_l) return get(2*id,l,mid,t_l,t_r); return get(2*id+1,mid+1,r,t_l,t_r); } }st; void precalc(){ stack<int> st; for(int i=n;i>=1;i--){ while(!st.empty()&&a[st.top()]<a[i]){ vR[i] = max(vR[i], a[st.top()]); st.pop(); } if(st.empty()){ R[i] = n; st.push(i); } else { if(a[st.top()]==a[i]){ R[i] = R[st.top()]; // vR[i] = max(vR[i], vR[st.top()]); } else { R[i] = st.top()-1; st.push(i); } } } } signed main(){ ios_base::sync_with_stdio(NULL); cin.tie(NULL); if(fopen("TASK.INP", "r")){ freopen("TASK.INP", "r", stdin); freopen("TASK.OUT", "w", stdout); } cin>>n>>q; for(int i=1;i<=n;i++) cin>>a[i]; precalc(); st.build(1,1,n); // cerr<<st.tr[1].best; // cerr<<st.get(1,1,n,5,n).best<<"\n"; while(q--){ int l,r,k; cin>>l>>r>>k; // cerr<<l<<" "<<r<<"\n"; int f= st.get(1,1,n,l,r).best; cout<<(f<=k)<<"\n"; // for(int i=l;i<=r;i++) cerr<<a[i]<<" "; // cerr<<"\n "<<f; } }

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen("TASK.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen("TASK.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...