Submission #904932

#	Time	Username	Problem	Language	Result	Execution time	Memory
904932		089487	Railway Trip 2 (JOI22_ho_t4)	C++14	100 / 100	1363 ms	510168 KiB

Main

#include<bits/stdc++.h>
#define int long long
#define quick ios::sync_with_stdio(0);cin.tie(0);
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define repd(x,a,b) for(int x=a;x>=b;x--)
#define lowbit(x) (x&-x)
#define sz(x) (int)(x.size())
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define mp make_pair
#define eb emplace_back
using namespace std;
typedef pair<int,int> pii;
void debug(){
    cout<<"\n";
}
template<class T,class ...U>
void debug(T a,U ...b){
    cout<<a<<" ",debug(b...);
}
const int N=2e5+7;
const int K=18;
const int INF=1e18;
pii dis[K][N];
pii ans[K][N*4];
pii tag[K][N*4];
pii p[N];
#define ll 2*x+1
#define rr 2*x+2
#define L ll,lx,mid
#define R rr,mid,rx
void Upd(pii &x,int val){
    x=mp(min(x.F,val),max(x.S,val));
}
void Upd(pii &x,pii val){
    x=mp(min(x.F,val.F),max(x.S,val.S));
}
void push(int i,int x,int lx,int rx){
    if(lx==rx-1||tag[i][x].F>tag[i][x].S){
        return ;
    }
    Upd(ans[i][ll],tag[i][x]);
    Upd(ans[i][rr],tag[i][x]);
    Upd(tag[i][ll],tag[i][x]);
    Upd(tag[i][rr],tag[i][x]);
    tag[i][x]=mp(INF,-INF);
}
void pull(int i,int x){
    ans[i][x]=mp(min(ans[i][ll].F,ans[i][rr].F),max(ans[i][ll].S,ans[i][rr].S));
}
void upd(int i,int x,int lx,int rx,int l,int r,int val){
    //debug("upd i,lx,rx,l,r,val",i,lx,rx,l,r,val);
    if(l<=lx&&rx<=r){
        Upd(ans[i][x],val);
        Upd(tag[i][x],val);
        return ;
    }
    if(l>=rx||lx>=r) return ;

    int mid=(lx+rx)>>1;
    push(i,x,lx,rx);
    upd(i,L,l,r,val);
    upd(i,R,l,r,val);
    pull(i,x);
    return ;
}
pii qry(int i,int x,int lx,int rx,int l,int r){
    if(l>r) return mp(INF,-INF);
    //debug("qry i lx,rx,l,r",i,lx,rx,l,r);
    if(l<=lx&&rx<=r) return ans[i][x];
    if(l>=rx||lx>=r) return mp(INF,-INF);
    int mid=(lx+rx)>>1;
    push(i,x,lx,rx);
    pii a=qry(i,L,l,r);
    pii b=qry(i,R,l,r);
    return mp(min(a.F,b.F),max(a.S,b.S));
}
void build(int i,int x,int lx,int rx){
    if(lx==rx-1){
        ans[i][x]=dis[i][lx];
        return ;
    }
    int mid=(lx+rx)>>1;
    build(i,L);
    build(i,R);
    pull(i,x);
}
signed main(){
	quick
    
    int n,k,m;
    cin>>n>>k>>m;
    rep(i,0,m-1) cin>>p[i].F>>p[i].S;
    fill(ans[0],ans[0]+N*4,mp(INF,-INF));
    fill(tag[0],tag[0]+N*4,mp(INF,-INF));
    rep(i,0,m-1){ 
        if(p[i].F<p[i].S){
            upd(0,0,1,n+1,p[i].F,min(p[i].F+k,p[i].S+1),p[i].S);
        }
        else{
            swap(p[i].F,p[i].S);
            //debug("upd",max(p[i].F,p[i].S-k+1),p[i].S+1,p[i].F);
            upd(0,0,1,n+1,max(p[i].F,p[i].S-k+1),p[i].S+1,p[i].F);
        }
    }
    //debug("ok");
    //return 0;
    rep(i,1,n){
        dis[0][i]=qry(0,0,1,n+1,i,i+1);
        Upd(dis[0][i],i);
    }
    build(0,0,1,n+1);
    rep(i,1,K-1){
        rep(j,1,n){
            dis[i][j]=qry(i-1,0,1,n+1,dis[i-1][j].F,dis[i-1][j].S+1);
            dis[i][j]=mp(min(dis[i][j].F,dis[i-1][j].F),max(dis[i][j].S,dis[i-1][j].S));
        }
        fill(ans[i],ans[i]+N*4,mp(INF,-INF));
        fill(tag[i],tag[i]+N*4,mp(INF,-INF));
        build(i,0,1,n+1);
    }
    /*rep(i,1,n){
        cout<<"("<<dis[0][i].F<<","<<dis[0][i].S<<")"<<" \n"[i==n];
    }*/
    int q;
    cin>>q;
    while(q--){
        int s,t;
        cin>>s>>t;
        if(s==t) {
            cout<<"0\n";
            continue;
        }
        pii now=mp(s,s);
        int step=0;
        repd(i,K-1,0){
            pii nxt=qry(i,0,1,n+1,now.F,now.S+1);
            //debug("now",now.F,now.S,"move",1<<i,nxt.F,nxt.S);
            if(nxt.F>t||nxt.S<t){
                //debug("do",now.F,now.S,"mv=>",nxt.F,nxt.S);
                step+=(1<<i);
                now=nxt;
            }
        }
        step+=1;
        now=qry(0,0,1,n+1,now.F,now.S+1);
        //debug("step",step,now.F,now.S);
        if(now.F>t||now.S<t) cout<<"-1\n";
        else cout<<step<<"\n";
        
    }
}

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