Submission #1287909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287909		quocbaoo	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	17 / 100	1351 ms	268472 KiB

sortbooks

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
int n,m,a[1000005];
namespace sub1{
    void xuly(){
        while (m--){
            int l,r,w;cin>>l>>r>>w;int ma=0;
            for (int i=l;i<=r;i++){
                for (int j=i+1;j<=r;j++){
                    if (a[i]>a[j]){
                        ma=max(ma,a[i]+a[j]);
                    }
                }
            }
            if (ma>w) cout<<"0"<<'\n';
            else cout<<"1"<<'\n';
        }
    }
}
namespace full{
    const int N=1e6;
    int ma[N+5][22],lg[N+5];pair<int,int> nex[N+5][22];
    int get(int l,int r){
        if (l>r) return -1e9;
        int k=lg[r-l+1];
        return max(ma[l][k],ma[r-(1<<k)+1][k]);
    }
    void xuly(){
        for (int i=2;i<=n;i++) lg[i]=lg[i/2]+1;
        for (int i=1;i<=n;i++) ma[i][0]=a[i];
        for (int j=1;j<=20;j++){
            for (int i=1;i<=n;i++){
                if (i+(1<<(j-1))>n) break;
                ma[i][j]=max(ma[i][j-1],ma[i+(1<<(j-1))][j-1]);
            }
        }
        stack<int> st;
        st.push(n+1);a[n+1]=1e9+8;
        for (int i=n;i>=1;i--){
            while (!st.empty()){
                if (a[i]>a[st.top()]) st.pop();
                else break;
            }
            nex[i][0]={st.top()-1,a[i]+get(i+1,st.top()-1)};
            st.push(i);
        }
        for (int j=0;j<=20;j++)  nex[n+1][j]={n+1,-1e9};
        for (int j=1;j<=20;j++){
            for (int i=1;i<=n;i++){
                if (nex[i][j-1].fi+1>n){
                    nex[i][j].fi=n+1;
                    nex[i][j].se=nex[i][j-1].se;continue;
                }
                nex[i][j].fi=nex[nex[i][j-1].fi+1][j-1].fi;
                nex[i][j].se=max(nex[i][j-1].se,nex[nex[i][j-1].fi+1][j-1].se);
            }
        }
//        cout<<nex[18][0].fi<<" "<<nex[16][1].se<<endl;
        while (m--){
            int l,r,w;cin>>l>>r>>w;
            if (l==r){
                cout<<"1"<<'\n';continue;
            }
            bool kt=false;int maa=-1e9;
            for (int j=20;j>=0;j--){
                if (nex[l][j].fi<=r){
                    maa=max(maa,nex[l][j].se);
                    l=nex[l][j].fi+1;
                }
            }
            if (l<r) maa=max(maa,a[l]+get(l+1,r));
            if (maa>w) cout<<"0"<<'\n';else cout<<"1"<<'\n';
        }
    }
}
int main(){
    if (fopen("sortbooks.inp","r")){
        freopen("sortbooks.inp","r",stdin);
        freopen("sortbooks.out","w",stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>a[i];
//    if (n<=500&&m<=500) return sub1::xuly(),0;
    full::xuly();
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen("sortbooks.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen("sortbooks.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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