Submission #671520

#	Time	Username	Problem	Language	Result	Execution time	Memory
671520		Darren0724	Railway Trip 2 (JOI22_ho_t4)	C++17	25 / 100	2068 ms	394832 KiB

Main

//challenge: 100
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define x first
#define y second
#define endl '\n'
int n,k,m;
const int INF=1e9;
vector<vector<int>> dp1,dp2;
struct segmax{
    int l,r,m;
    int val=-INF;
    int lz=-INF;
    segmax *lc,*rc;
    segmax(int l1,int r1){
        l=l1,r=r1;
        m=(l+r)>>1;
        if(r-l==1){
            return;
        }
        lc=new segmax(l,m);
        rc=new segmax(m,r);
    }
    int rv(){
        if(lz==-INF){
            return val;
        }
        return max(val,lz);
    }
    void pull(){
        val=max({lc->rv(),rc->rv(),val});
    }
    void push(){
        if(lz!=-INF){
            lc->lz=max(lc->lz,lz);
            rc->lz=max(rc->lz,lz);
            lz=-INF;
        }
        pull();
    }
    void add(int a,int b,int x){
        if(a<=l&&b>=r){
            lz=max(lz,x);
            return;
        }
        push();
        if(a<m){
            lc->add(a,b,x);
        }
        if(b>m){
            rc->add(a,b,x);
        }
        pull();
    }
    int query(int a,int b){
        if(a<=l&&b>=r){
            return rv();
        }
        push();
        int ans=-INF;
        if(a<m){
            ans=max(ans,lc->query(a,b));
        }
        if(b>m){
            ans=max(ans,rc->query(a,b));
        }
        pull();
        return ans;
    }
};
struct segmin{
    int l,r,m;
    int val=INF;
    int lz=INF;
    segmin *lc,*rc;
    segmin(int l1,int r1){
        l=l1,r=r1;
        m=(l+r)>>1;
        if(r-l==1){
            return;
        }
        lc=new segmin(l,m);
        rc=new segmin(m,r);
    }
    int rv(){
        if(lz==INF){
            return val;
        }
        return min(val,lz);
    }
    void pull(){
        val=min({lc->rv(),rc->rv(),val});
    }
    void push(){
        if(lz!=INF){
            lc->lz=min(lc->lz,lz);
            rc->lz=min(rc->lz,lz);
            lz=INF;
        }
        pull();
    }
    void add(int a,int b,int x){
        if(a<=l&&b>=r){
            lz=min(lz,x);
            return;
        }
        push();
        if(a<m){
            lc->add(a,b,x);
        }
        if(b>m){
            rc->add(a,b,x);
        }
        pull();
    }
    int query(int a,int b){
        if(a<=l&&b>=r){
            return rv();
        }
        push();
        int ans=INF;
        if(a<m){
            ans=min(ans,lc->query(a,b));
        }
        if(b>m){
            ans=min(ans,rc->query(a,b));
        }
        pull();
        return ans;
    }
};
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k>>m;
    dp1.resize(20,vector<int>(n));
    dp2.resize(20,vector<int>(n));
    segmax *rt=new segmax(0,n);
    segmin *rt1=new segmin(0,n);
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        a--;b--;
        if(a<b){
            int c=min(b-1,a+k-1);
            rt->add(a,c+1,b);
        }
        else{
            int c=max(b+1,a-k+1);
            rt1->add(c,a+1,b);
        }
    }
    for(int i=0;i<n;i++){
        rt->add(i,i+1,i);
        rt1->add(i,i+1,i);
    }
    for(int i=0;i<n;i++){
        dp1[0][i]=rt1->query(i,i+1);
        dp2[0][i]=rt->query(i,i+1);
    }
    for(int i=1;i<20;i++){
        segmax *mx=new segmax(0,n);
        segmin *mn=new segmin(0,n);
        for(int j=0;j<n;j++){
            mx->add(j,j+1,dp2[i-1][j]);
            mn->add(j,j+1,dp1[i-1][j]);
        }
        for(int j=0;j<n;j++){
            dp1[i][j]=mn->query(dp1[i-1][j],dp2[i-1][j]+1);
            dp2[i][j]=mx->query(dp1[i-1][j],dp2[i-1][j]+1);
        }
    }
    int q;cin>>q;
    for(int i=0;i<q;i++){
        int a,b;cin>>a>>b;
        a--;b--;
        if(a<b){
            if(dp2[19][a]<b){
                cout<<-1<<endl;
            }
            else{
                int ans=0;
                for(int j=19;j>=0;j--){
                    if(dp2[j][a]<b){
                        ans+=(1<<j);
                        a=dp2[j][a];
                    }
                }
                cout<<ans+1<<endl;
            }
        }
        else{
            if(dp1[19][a]>b){
                cout<<-1<<endl;
            }
            else{
                int ans=0;
                for(int j=19;j>=0;j--){
                    if(dp1[j][a]>b){
                        ans+=(1<<j);
                        a=dp1[j][a];
                    }
                }
                cout<<ans+1<<endl;
            }
        }
    }
 
    return 0;
}

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