Submission #442987

#	Time	Username	Problem	Language	Result	Execution time	Memory
442987		zaneyu	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	64 / 100	3083 ms	238080 KiB

sortbooks

/*input
5 2
3 5 1 8 2
1 3 6
2 5 3
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
const int maxn=1e6+5;
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define sz(x) (int)x.size()
int arr[maxn];
vector<int> seg[4*maxn];
int cst[4*maxn];
inline void build(int idx,int l,int r){
    if(l==r){
        cst[idx]=0;
        seg[idx].pb(arr[l]);
        return;
    }
    int mid=(l+r)/2;
    build(idx*2,l,mid);
    build(idx*2+1,mid+1,r);
    seg[idx].resize(sz(seg[idx*2])+sz(seg[idx*2+1]));
    merge(ALL(seg[idx*2]),ALL(seg[idx*2+1]),seg[idx].begin());
    auto z=lower_bound(ALL(seg[idx*2+1]),seg[idx*2].back());
    int cur=0;
    if(z!=seg[idx*2+1].begin()){
        z--;
        cur=(*z)+seg[idx*2].back();
    }
    cst[idx]=max({cst[idx*2],cst[idx*2+1],cur});
    //cout<<l<<' '<<r<<' '<<cst[idx]<<'\n';
}
int mx=0;
int ans=0;
inline void query(int idx,int l,int r,int ql,int qr){
    if(r<ql or l>qr) return;
    if(ql<=l and r<=qr){
        auto z=(lower_bound(ALL(seg[idx]),mx));
        MXTO(ans,cst[idx]);
        if(z==seg[idx].begin()){
            MXTO(mx,seg[idx].back());
            return;
        }
        z=prev(z);
        MXTO(ans,(*z)+mx);
        MXTO(mx,seg[idx].back());
        return;
    }
    int mid=(l+r)/2;
    query(idx*2,l,mid,ql,qr);
    query(idx*2+1,mid+1,r,ql,qr);
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,q;
    cin>>n>>q;
    REP(i,n) cin>>arr[i];
    build(1,0,n-1);
    while(q--){
        int l,r,k;
        cin>>l>>r>>k;
        --l;
        --r;
        mx=0,ans=0;
        query(1,0,n-1,l,r);
        //cout<<ans<<'\n';
        cout<<(ans<=k)<<'\n';
    }
}

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