Submission #1274735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274735		nthvn	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	1087 ms	31168 KiB

sortbooks

#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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23