Submission #593762

#	Time	Username	Problem	Language	Result	Execution time	Memory
593762		oleh1421	Railway Trip 2 (JOI22_ho_t4)	C++17	27 / 100	2071 ms	38248 KiB

Main

//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#define y2 y_2
//#define endl '\n'
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
const ll inf=1e18;
mt19937 rnd(time(NULL));
const ll mod=998244353;
const int N=200010;
const int Lg=20;
int lg[N];
vector<int>addR[N];
vector<int>addL[N];
int l[N],r[N];
pair<int,int>up[N][Lg];
struct SparseTable{
    int mult;
    int a[N];
    int best[Lg][N];
    int n;
    void build(){
        for (int i=1;i<=n;i++) a[i]*=mult;
        for (int i=1;i<=n;i++) best[0][i]=i;
        for (int j=1;j<Lg;j++){
            for (int i=1;i<=n-(1<<j)+1;i++){
                int x=best[j-1][i];
                int y=best[j-1][i+(1<<(j-1))];
                if (a[x]>a[y]) best[j][i]=x;
                else best[j][i]=y;

            }
        }

    }
    int get(int l,int r){
        int len=lg[r-l+1];
        int x=best[len][l];
        int y=best[len][r-(1<<len)+1];
//        if (l+(1<<len)-1>n) exit(1);
        if (a[x]>a[y]) return x;
        return y;
    }
};
SparseTable L;
SparseTable R;
void solve(){
    int n,k,m;cin>>n>>k>>m;
    for (int i=1;i<=m;i++){
        int a,b;cin>>a>>b;
        if (a<b){
            int l=a;
            int r=min(a+k-1,b-1);
            addR[l].push_back(b);
            addR[r+1].push_back(-b);
        } else {
            swap(a,b);
            int r=b;
            int l=max(a+1,b-k+1);
            addL[r].push_back(a);
            addL[l-1].push_back(-a);

        }
    }
    multiset<int>st;
    for (int i=1;i<=n;i++){
        for (int x:addR[i]){
            if (x<0) st.erase(st.find(-x));
            else st.insert(x);
        }
        r[i]=i;
        if (!st.empty()) r[i]=max(r[i],(*st.rbegin()));
    }
    st.clear();
    for (int i=n;i>=1;i--){
        for (int x:addL[i]){
            if (x<0) st.erase(st.find(-x));
            if (x>0) st.insert(x);
        }
        l[i]=i;
        if (!st.empty()) l[i]=min(l[i],(*st.begin()));
    }
    L.mult=-1;
    R.mult=1;
    L.n=R.n=n;
    for (int i=1;i<=n;i++){
//        cout<<i<<" "<<l[i]<<" "<<r[i]<<'\n';
        L.a[i]=l[i];
        R.a[i]=r[i];
    }
    L.build();
    R.build();

    int q;cin>>q;
    for (int i=1;i<=q;i++){
        int s,t;cin>>s>>t;
        int sL=s,sR=s;
        int res=0;
        while (t<sL || t>sR){
            int nwL=l[L.get(sL,sR)];
            int nwR=r[R.get(sL,sR)];
            if (nwL==sL && nwR==sR) break;
//            cout<<sL<<" "<<sR<<" "<<nwL<<" "<<nwR<<" "<<L.get(sL,sR)<<endl;


            sL=nwL;
            sR=nwR;
            res++;
        }
        if (sL<=t && t<=sR) cout<<res<<'\n';
        else cout<<-1<<'\n';
    }

}
int32_t main() {

    lg[1]=0;
    for (int i=2;i<N;i++) lg[i]=lg[i/2]+1;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt=1;
//    cin>>tt;
    while (tt--){
        solve();
    }
    return 0;

}


/**
3
5 2 7 3 1 6 8 4
**/

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