Submission #887760

#	Time	Username	Problem	Language	Result	Execution time	Memory
887760		owoovo	Railway Trip 2 (JOI22_ho_t4)	C++14	100 / 100	1485 ms	136300 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 MP(min(a.F,b.F),max(a.S,b.S));
}
pair<int,int> iit={maxn,0};
int fl[100010][20],fr[100010][20],n,m,k;
struct node{
    pair<int,int> val,tag;
};
struct seg{
    node tri[400010];
    void push(int l,int r,int id){ 
        if(tri[id].tag!=iit){
            tri[id].val=tri[id].tag+tri[id].val;
            if(l!=r){
                tri[lc].tag=tri[lc].tag+tri[id].tag;
                tri[rc].tag=tri[rc].tag+tri[id].tag;
            }
            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;
        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].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);
        }
    }
}tree[20];

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;
    }
    tree[0].build(1,n,0,0);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        if(a<b){
            tree[0].modify(1,n,a,min(a+k-1,b),0,b);
        }else{
            tree[0].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=tree[i-1].query(1,n,fl[j][i-1],fr[j][i-1],0);
            fl[j][i]=now.F;
            fr[j][i]=now.S;
        }
        tree[i].build(1,n,0,i);
    }
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        int s,t,ans=0;
        cin>>s>>t;
        pair<int,int> now={s,s};
        if(s<t){
            if(fr[s][18]<t){
                cout<<"-1\n";
                continue;
            }
            for(int j=18;j>0;j--){
                if(tree[j].query(1,n,now.F,now.S,0).S<t){
                    ans+=1<<(j-1);
                    now=tree[j].query(1,n,now.F,now.S,0);
                }
            }
            cout<<ans+1<<"\n";
        }else{
            if(fl[s][18]>t){
                cout<<"-1\n";
                continue;
            }
            for(int j=18;j>0;j--){
                if(tree[j].query(1,n,now.F,now.S,0).F>t){
                    ans+=1<<(j-1);
                    now=tree[j].query(1,n,now.F,now.S,0);
                }
            }
            cout<<ans+1<<"\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