Submission #887752

#	Time	Username	Problem	Language	Result	Execution time	Memory
887752		owoovo	Railway Trip 2 (JOI22_ho_t4)	C++14	36 / 100	835 ms	24404 KiB

Main

#include<bits/stdc++.h>
#define F first 
#define S second
#define lc id*2+1
#define rc id*2+2
#define MP make_pair
using namespace std;
const int maxn=1e6;
pair<int,int> operator+(pair<int,int> a,pair<int,int> b){
    return {min(a.F,b.F),max(a.S,b.S)};
}
pair<int,int> iit={maxn,0};
struct node{
    pair<int,int> val,tag;
    int ist=0;
};
int fl[100010][20],fr[100010][20],n,m,k;
node tri[400010];
void push(int l,int r,int id){ 
    if(tri[id].ist){
        tri[id].val=tri[id].tag+tri[id].val;
        if(l!=r){
            tri[lc].ist=1;
            tri[rc].ist=1;
            tri[lc].tag=tri[lc].tag+tri[id].tag;
            tri[rc].tag=tri[rc].tag+tri[id].tag;
        }
        tri[id].ist=0;
        tri[id].tag=iit;
    }
    return;
}
void pull(int l,int r,int id){
    push(l,r,id);
    if(l!=r){
        int m=(l+r)>>1;
        push(l,m,lc);
        push(m+1,r,rc);
        tri[id].val=tri[lc].val+tri[rc].val;
    }
    return;
}
void build(int l,int r,int id,int i){
    tri[id].tag=iit;
    tri[id].ist=0;
    if(l==r){
        tri[id].val={fl[l][i],fr[l][i]};
        return;
    }
    int m=(l+r)>>1;
    build(l,m,lc,i);
    build(m+1,r,rc,i);
    pull(l,r,id);
}
void modify(int l,int r,int L,int R,int id,int x){
    pull(l,r,id);
    if(l==L&&r==R){
        tri[id].ist=1;
        tri[id].tag=tri[id].tag+MP(x,x);
        return;
    }
    int m=(l+r)>>1;
    if(R<=m){
        modify(l,m,L,R,lc,x);
    }else if(L>m){
        modify(m+1,r,L,R,rc,x);
    }else{
        modify(l,m,L,m,lc,x);
        modify(m+1,r,m+1,R,rc,x);
    }
    pull(l,r,id);
    return;
}
pair<int,int> query(int l,int r,int L,int R,int id){
    pull(l,r,id);
    if(l==L&&r==R){
        return tri[id].val;
    }
    int m=(l+r)>>1;
    if(R<=m){
        return query(l,m,L,R,lc);
    }else if(L>m){
        return query(m+1,r,L,R,rc);
    }else{
        return query(l,m,L,m,lc)+query(m+1,r,m+1,R,rc);
    }
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>k>>m;
    for(int j=1;j<=n;j++){
        fl[j][0]=j;
        fr[j][0]=j;
    }
    build(1,n,0,0);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        if(a<b){
            modify(1,n,a,min(a+k-1,b),0,b);
        }else{
            modify(1,n,max(a-k+1,b),a,0,b);
        }
    }
    for(int i=1;i<=18;i++){
        for(int j=1;j<=n;j++){
            auto now=query(1,n,fl[j][i-1],fr[j][i-1],0);
            fl[j][i]=now.F;
            fr[j][i]=now.S;
        }
        build(1,n,0,i);
    }
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        int s,t,ans=0;
        cin>>s>>t;
        if(s<t){
            if(fr[s][18]<t){
                cout<<"-1\n";
                continue;
            }
            for(int j=18;j>0;j--){
                if(fr[s][j]<t){
                    ans+=1<<(j-1);
                    s=fr[s][j];
                }
            }
            cout<<ans+1<<"\n";
        }else{
            if(fl[s][18]>t){
                cout<<"-1\n";
                continue;
            }
            for(int j=18;j>0;j--){
                if(fl[s][j]>t){
                    ans+=1<<(j-1);
                    s=fl[s][j];
                }
            }
            cout<<ans+1<<"\n";
        }
    }
    return 0;
}

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