Submission #1188069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188069		user736482	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	1910 ms	243228 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL
#define POT (1<<20)
ll a,b,c,d,t,n,m,l,q,k,ak;
ll sgtree[POT][2][20];
vector<pair<ll,ll>>op,op2;
multiset<ll>s;
pair<ll,ll>sg[250007][20];
ll get(ll pocz,ll kon,ll l,ll r,ll v,bool czymx,ll idx){
    if(pocz>r || kon<l)return INFL*(!czymx);
    if(pocz<=l && kon>=r){
        return sgtree[v][czymx][idx];
    }
    else{
        if(czymx)return max(
        get(pocz,kon,l,(l+r)/2,v*2,czymx,idx),
        get(pocz,kon,(l+r)/2+1,r,v*2+1,czymx,idx));
        else return min(get(pocz,kon,l,(l+r)/2,v*2,czymx,idx),
        get(pocz,kon,(l+r)/2+1,r,v*2+1,czymx,idx));
    }
}
void update(ll v,ll idx){
    sgtree[v][0][idx]=min(sgtree[v*2][0][idx],sgtree[v*2+1][0][idx]);
    sgtree[v][1][idx]=max(sgtree[v*2][1][idx],sgtree[v*2+1][1][idx]);
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k>>m;
    for(ll i=0;i<m;i++){
        cin>>a>>b;
        a--;
        b--;
        if(a<b){
            op.pb({a,b});
            op.pb({min(b+1,a+k),b+INFL});
        }
        else{
            op2.pb({a,b});
            op2.pb({max(b-1,a-k),b+INFL});
        }
    }
    sort(op.begin(),op.end());
    sort(op2.begin(),op2.end());
    reverse(op.begin(),op.end());
    for(ll i=0;i<n;i++){
        while(op.size() && op.back().ff==i){
            if(op.back().ss>=INFL){
                s.erase(s.lower_bound(op.back().ss-INFL));
            }
            else{
                s.insert(op.back().ss);
            }
            op.pop_back();
        }
       s.insert(i);
        sg[i][0].ss=(*--s.end());
        s.erase(s.lower_bound(i));
    }
    for(ll i=n-1;i>=0;i--){
        while(op2.size() && op2.back().ff==i){
            if(op2.back().ss>=INFL){
                s.erase(s.lower_bound(op2.back().ss-INFL));
            }
            else{
                s.insert(op2.back().ss);
            }
            op2.pop_back();
        }
        s.insert(i);
        sg[i][0].ff=(*s.begin());
        s.erase(s.lower_bound(i));
    }
    for(ll j=1;j<20;j++){
        for(ll i=0;i<n;i++){
            sgtree[i+POT/2][0][j-1]=sg[i][j-1].ff;
            sgtree[i+POT/2][1][j-1]=sg[i][j-1].ss;
        }
        for(ll i=POT/2-1;i>=1;i--)update(i,j-1);
        for(ll i=0;i<n;i++)sg[i][j]={get(sg[i][j-1].ff,sg[i][j-1].ss,0,POT/2-1,1,0,j-1),get(sg[i][j-1].ff,sg[i][j-1].ss,0,POT/2-1,1,1,j-1)};
    }
    cin>>q;
    for(ll i=0;i<q;i++){
        cin>>a>>b;
        a--;
        b--;
        pair<ll,ll>curr={a,a};
        ll ans=1;
        ll ak=18;
        if(sg[a][18].ss<b || sg[a][18].ff>b){
            cout<<"-1\n";
            continue;
        }
        while(1){
            while(get(curr.ff,curr.ss,0,POT/2-1,1,0,ak)<=b && get(curr.ff,curr.ss,0,POT/2-1,1,1,ak)>=b){
                ak--;
                if(ak<0)break;
            }
            if(ak<0)break;
            ans+=(1<<ak);
            curr={get(curr.ff,curr.ss,0,POT/2-1,1,0,ak),get(curr.ff,curr.ss,0,POT/2-1,1,1,ak)};
        }
        cout<<ans<<"\n";
    }
    return 0;
}

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