Submission #593776

#	Time	Username	Problem	Language	Result	Execution time	Memory
593776		oleh1421	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	500 ms	55764 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=21;
int lg[N];
vector<int>addR[N];
vector<int>addL[N];
int l[N],r[N];
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;
pair<int,int>up[Lg][N];

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();
    for (int i=1;i<=n;i++){
        up[0][i]={L.get(l[i],r[i]),R.get(l[i],r[i])};
    }
    for (int j=1;j<=Lg;j++){
        for (int i=1;i<=n;i++){
            ///calc up[j][i]
            vector<int>consider;
            consider.push_back(up[j-1][up[j-1][i].first].first);
            consider.push_back(up[j-1][up[j-1][i].first].second);
            consider.push_back(up[j-1][up[j-1][i].second].first);
            consider.push_back(up[j-1][up[j-1][i].second].second);
            up[j][i]=up[j-1][i];
            for (int x:consider){
                if (l[x]<l[up[j][i].first]) up[j][i].first=x;
                if (r[x]>r[up[j][i].second]) up[j][i].second=x;
            }
        }
    }
    int q;cin>>q;
    for (int i=1;i<=q;i++){
        int s,t;cin>>s>>t;
        if (l[up[Lg-1][s].first]>t || r[up[Lg-1][s].second]<t){
            cout<<-1<<'\n';
            continue;
        }
        if (l[s]<=t && t<=r[s]){
            cout<<1<<'\n';
            continue;
        }
        int res=0;
        int sL=s,sR=s;
        for (int j=Lg-1;j>=0;j--){
            int nwL=sL;
            int nwR=sR;
            vector<int>consider;
            consider.push_back(up[j][sL].first);
            consider.push_back(up[j][sL].second);
            consider.push_back(up[j][sR].first);
            consider.push_back(up[j][sR].second);
            for (int x:consider){
                if (l[x]<l[nwL]) nwL=x;
                if (r[x]>r[nwR]) nwR=x;
            }
            if (l[nwL]>t || r[nwR]<t){
                res+=(1<<j);
                sL=nwL;
                sR=nwR;
            }
        }
        res+=2;
        cout<<res<<'\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: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13