Submission #1035356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035356		alexander707070	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2093 ms	118104 KiB

sortbooks

#include<bits/stdc++.h>
#define MAXN 1000007
using namespace std;

const int inf=1e9+7;

struct event{
    int r,k,id;
};

int n,w[MAXN],q,l,r,k[MAXN],ans[MAXN];
vector<event> qs[MAXN];

int tree[4*MAXN],maxs[4*MAXN];

void build(int v,int l,int r){
    if(l==r){
        tree[v]=w[l];
    }else{
        int tt=(l+r)/2;
        build(2*v,l,tt);
        build(2*v+1,tt+1,r);

        tree[v]=max(tree[2*v],tree[2*v+1]);
    }
}

int getmax(int v,int l,int r,int ll,int rr){
    if(ll>rr)return 0;
    if(l==ll and r==rr)return tree[v];

    int tt=(l+r)/2;
    return max( getmax(2*v,l,tt,ll,min(tt,rr)) , getmax(2*v+1,tt+1,r,max(tt+1,ll),rr) );
}

void update(int v,int l,int r,int pos,int val){
    if(l==r){
        maxs[v]=val;
    }else{
        int tt=(l+r)/2;
        if(pos<=tt)update(2*v,l,tt,pos,val);
        else update(2*v+1,tt+1,r,pos,val);

        maxs[v]=max(maxs[2*v],maxs[2*v+1]);
    }
}

int getval(int v,int l,int r,int ll,int rr){
    if(ll>rr)return 0;
    if(l==ll and r==rr)return maxs[v];

    int tt=(l+r)/2;
    return max( getval(2*v,l,tt,ll,min(tt,rr)) , getval(2*v+1,tt+1,r,max(tt+1,ll),rr) );
}

vector< pair<int,int> > st;


int main(){

    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>w[i];
    }
    build(1,1,n);

    for(int i=1;i<=q;i++){
        cin>>l>>r>>k[i];
        qs[l].push_back({r,k[i],i});
    }

    st.push_back({n+1,0});
    w[n+1]=inf;

    for(int i=n;i>=1;i--){
        pair<int,int> curr={i,0};

        while(!st.empty() and w[i]>w[st.back().first]){
            curr.second=w[i]+w[st.back().first];
            st.pop_back();
        }

        st.push_back(curr);
        update(1,0,n,st.size()-1,curr.second);

        for(int f=0;f<qs[i].size();f++){

            int lt=0,rt=st.size(),tt;

            while(lt+1<rt){
                tt=(lt+rt)/2;
                if(st[tt-1].first<=qs[i][f].r){
                    rt=tt;
                }else{
                    lt=tt;
                }
            }

            if(rt<st.size()) ans[qs[i][f].id]=getval(1,0,n,rt,st.size()-1);
            if(rt>1){
                rt--;
                if(st[rt].first+1<=qs[i][f].r){
                    int s=getmax(1,1,n,st[rt].first+1,qs[i][f].r);
                    ans[qs[i][f].id]=max(ans[qs[i][f].id],w[st[rt].first]+s);
                }
            }
        }
    }

    for(int i=1;i<=q;i++){
        if(ans[i]>k[i])cout<<"0\n";
        else cout<<"1\n";
    }

    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for(int f=0;f<qs[i].size();f++){
      |                     ~^~~~~~~~~~~~~
sortbooks.cpp:99:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |             if(rt<st.size()) ans[qs[i][f].id]=getval(1,0,n,rt,st.size()-1);
      |                ~~^~~~~~~~~~

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