Submission #438708

#	Time	Username	Problem	Language	Result	Execution time	Memory
438708		leaked	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	3043 ms	230480 KiB

sortbooks

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define f first
#define s second
#define endl '\n'
#define vec vector
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define m_p make_pair
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

auto rng=bind(uniform_int_distribution<int>(0,1e9),mt19937(time(0)));

template<class T>bool umin(T &a,const T &b) {return (a>b?a=b,1:0);}
template<class T>bool umax(T &a,const T &b) {return (a<b?a=b,1:0);}

template<class T> using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int N=1e6+1;
struct tr{
    int mxA=-1e9,mxB=-1e9,mxs=-2;
    void apply(int x){
        umax(mxs,x+mxA);
        umax(mxB,x);
    }
    void mg(tr &a,tr &b){
        mxA=max(a.mxA,b.mxA);
        mxs=max({a.mxs,b.mxs,mxB+mxA});
    }
};
tr ans,emp;
struct tree1{
    tr t[4*N];
    int p[4*N];
    tree1(){
        fill(p,p+4*N,-1);
        assert(t[0].mxs==-2);
    }
    void push(int v,int tl,int tr){
        if(p[v]==-1 || tl==tr) return;
        t[2*v].apply(p[v]);
        t[2*v+1].apply(p[v]);
        umax(p[2*v],p[v]);
        umax(p[2*v+1],p[v]);
        p[v]=-1;
    }
    void upda(int id,int x,int v,int tl,int tr){
        if(tl==tr){
            t[v].mxA=x;
            t[v].mxs=(x==-1e9?-2:x+t[v].mxB);
            return;
        }
        push(v,tl,tr);
        int tm=(tl+tr)>>1;
        if(tm>=id) upda(id,x,2*v,tl,tm);
        else upda(id,x,2*v+1,tm+1,tr);
        t[v].mg(t[2*v],t[2*v+1]);
    }
    void updb(int l,int r,int x,int v,int tl,int tr){
        if(tl>=l && tr<=r){
            t[v].apply(x);umax(p[v],x);
            return;
        }
        if(tl>r || tr<l) return;
        int tm=(tl+tr)>>1;push(v,tl,tr);
        updb(l,r,x,2*v,tl,tm);
        updb(l,r,x,2*v+1,tm+1,tr);
        t[v].mg(t[2*v],t[2*v+1]);
    }
    void get(int l,int r,int v,int tl,int tr){
        if(tl>=l && tr<=r){
            ans.mg(t[2*v],ans);
            return;
        }
        if(tl>r || tr<l) return ;
        push(v,tl,tr);
        int tm=(tl+tr)>>1;
        get(l,r,2*v,tl,tm);get(l,r,2*v+1,tm+1,tr);
    }
}C;
struct tree{
    int t[4*N];
    tree(){
        fill(t,t+4*N,-1);
    }
    void upd(int id,int x,int v,int tl,int tr){
        if(tl==tr){
            t[v]=x;return;
        }
        int tm=(tl+tr)>>1;
        if(tm>=id) upd(id,x,2*v,tl,tm);
        else upd(id,x,2*v+1,tm+1,tr);
        t[v]=max(t[2*v],t[2*v+1]);
    }
    int get(int l,int r,int v,int tl,int tr){
        if(tl>=l && tr<=r){
            return t[v];
        }
        if(tl>r || tr<l) return -1;
        int tm=(tl+tr)>>1;
        return max(get(l,r,2*v,tl,tm),get(l,r,2*v+1,tm+1,tr));
    }
}A,B;
int lft[N],rgt[N];
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//    ifstream cin("input.txt");
//    ifstream fin("o.txt");
    int n,q;
    cin>>n>>q;
    vec<int>a(n);
    for(auto &z : a) cin>>z;
    vec<pii>vc;vc.pb({2e9,-1});
    for(int i=0;i<n;i++){
        while(sz(vc) && a[i]>vc.back().f) vc.pop_back();
        lft[i]=vc.back().s;
        vc.pb({a[i],i});
        A.upd(i,a[i],1,0,n-1);
    }
    vc.clear();vc.pb({2e9,n});
    for(int i=n-1;i>=0;i--){
        while(sz(vc) && a[i]>vc.back().f) vc.pop_back();
        rgt[i]=vc.back().s;
        vc.pb({a[i],i});
    }
    vec<vec<int>>qry(n,vec<int>());
    vec<int>l(q),r(q),k(q),answ(q);
    for(int i=0;i<q;i++){
        cin>>l[i]>>r[i]>>k[i];--l[i];--r[i];
        qry[r[i]].pb(i);
    }
    vec<vec<int>>del(n+1,vec<int>());
    for(int i=0;i<n;i++){
        del[rgt[i]].pb(i);
        C.upda(i,a[i],1,0,n-1);
        for(auto &z : del[i]){
            B.upd(z,A.get(z+1,i-1,1,0,n-1),1,0,n-1);
            C.upda(z,-1e9,1,0,n-1);
        }
        /// also i need to update C
        C.updb(lft[i],i-1,a[i],1,0,n-1);
        for(auto &z : qry[i]){
            ans=emp;C.get(l[z],i,1,0,n-1);
            answ[z]=max(ans.mxs,B.get(z,i,1,0,n-1));
        }
    }
    for(int i=0;i<q;i++){
        cout<<(answ[i]<=k[i])<<endl;
    }
    return  0;
}
/*

*/

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