Submission #1200012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200012		JuanJL	Railway Trip 2 (JOI22_ho_t4)	C++20	35 / 100	817 ms	81884 KiB

Main

#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i < b; i++)
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset(a,v,sizeof(a))
using namespace std;
typedef long long ll;

#define NEUT (ll)-1

struct STree{
    ll n; 
    vector<ll> st;
    STree(ll n=0):n(n),st(4*n+5,-1){}
    void upd(ll k,ll l,ll r, ll p, ll v){
        if(l+1==r){ st[k]=v; return; }
        ll mid = (l+r)/2;
        if(mid>p) upd(2*k,l,mid,p,v);
        else upd(2*k+1,mid,r,p,v);
        st[k]=max(st[2*k],st[2*k+1]);
    }
    ll query(ll k,ll l,ll r,ll L,ll R){
        if(l>=R||r<=L) return NEUT;
        if(l>=L&&r<=R) return st[k];
        ll mid = (l+r)/2;
        return max(query(2*k,l,mid,L,R),query(2*k+1,mid,r,L,R));
    }
    void upd(ll p,ll v){ upd(1,0,n,p,v); }
    ll query(ll l,ll r){ return query(1,0,n,l,r); }
};

const int MAXN = 200000+5;
const int MAXP = 20;

ll n,k,m;
ll aa[MAXN];
ll bb[MAXN];

ll blift[MAXN][MAXP];
STree st[MAXP];
void precalc(){
    vector<pair<ll,ll>> orden={};
    forn(i,0,m){
        orden.pb({aa[i],bb[i]});
        orden.pb({aa[i]+k-1,bb[i]*-1});
    }

    sort(ALL(orden));
    reverse(ALL(orden));

    multiset<ll> vals;
    queue<ll> era;
    forn(i,1,n+1){
        while(!orden.empty() && orden.back().fst<=i){
            pair<ll,ll> aux = orden.back();
            //cout<<aux.fst<<" __ "<<aux.snd<<'\n';
            if(aux.snd>0) vals.insert(aux.snd*-1);
            else era.push(aux.snd);
            orden.pop_back();
        }

        ll val;
        if(vals.empty()) val=i;
        else val=abs(*vals.begin());

        //cout<<i<<" "<<val<<'\n';
        st[0].upd(i,val);
        //cout<<st[0].query(i,i+1)<<'\n';

        /*cout<<"--\n";
        for(auto j:vals) cout<<j<<" "; cout<<'\n';
        cout<<"--\n";*/

        while(!era.empty()){
            val = era.front();
            vals.erase(vals.find(val));
            era.pop();
        }
    }

    forn(p,1,MAXP){
        forn(i,1,n+1){
            st[p].upd(i,st[p-1].query(i,st[p-1].query(i,i+1)+1));
            //cout<<i<<" "<<p<<" -> "<<st[p].query(i,i+1)<<'\n';
        }
    }
}


int main(){
    cin>>n>>k>>m;
    mset(aa,-1); mset(bb,-1);
    forn(i,0,m) cin>>aa[i]>>bb[i];

    forn(i,0,MAXP){
        st[i]=STree(n+5);
    }

    precalc();

    ll q; cin>>q;
    while(q--){
        ll ini,fin; cin>>ini>>fin;
        ll l = ini; ll r = l+1;
        ll res = 0;
        for(int p = MAXP-1; p>=0; p--){
            ll qry = st[p].query(l,r);
            if(qry<fin){
                r=qry+1;
                res+=1<<p;
            }
        }

        if(st[MAXP-1].query(ini,ini+1)<fin) res=-2;

        cout<<res+1<<'\n';
    }
    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 11
• Subtask 4: 0 / 25
• Subtask 5: 35 / 35
• Subtask 6: 0 / 13