Submission #703383

#	Time	Username	Problem	Language	Result	Execution time	Memory
703383		Aestivate	Railway Trip 2 (JOI22_ho_t4)	C++17	27 / 100	2087 ms	13644 KiB

Main

#include<bits/stdc++.h>
#include<random>

using namespace std;

template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);

#define ss(n) fixed<<setprecision(n)
#define ll long long
#define int ll
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define ld long double
#define pb push_back
#define pii pair<int,int>
#define rep(i,a) for(int i=1;i<=a;i++)
#define rep0(i,a) for(int i=0;i<a;i++)
#define F first
#define S second
#define float double

ll gcd(ll a,ll b){if(b==0) return a; return gcd(b,a%b);}

const ld pi=3.14159265358979323846264338327950288419716939931;
const int lar=3e18;
const int mol1=1e9+7;
const int mol2=998224353;
const int mol3=1e15+9;
const int bb=137;

int mxl[400005],mxr[400005],lal1[400005]={0},lal2[400005];

void build(int l,int r,int ind){
    if(l==r){
        mxl[ind]=l;mxr[ind]=l;
        return;
    }
    int mid=l+r>>1;
    build(l,mid,ind*2);build(mid+1,r,ind*2+1);
    mxl[ind]=min(mxl[ind*2],mxl[ind*2+1]);
    mxr[ind]=max(mxr[ind*2],mxr[ind*2+1]);
}

void upd1(int l,int r ,int l1,int r1,int vv,int ind){
    if(l1<=l&&r<=r1) {
        lal1[ind]=min(lal1[ind],vv);
        mxl[ind]=min(mxl[ind],vv);
        return;
    }
    int mid=l+r>>1;
    if(lal1[ind]!=lar){
        int p=lal1[ind];lal1[ind]=lar;
        lal1[ind*2]=min(lal1[ind*2],p);
        lal1[ind*2+1]=min(lal1[ind*2+1],p);mxl[ind*2]=min(mxl[ind*2],p);
        mxl[ind*2+1]=min(mxl[ind*2+1],p);
    }
    if(r1<=mid) upd1(l,mid,l1,r1,vv,ind*2);
    else if(l1>mid) upd1(mid+1,r,l1,r1,vv,ind*2+1);
    else{
        upd1(l,mid,l1,r1,vv,ind*2);upd1(mid+1,r,l1,r1,vv,ind*2+1);
    }
    mxl[ind]=min(mxl[ind*2],mxl[ind*2+1]);
}

void upd2(int l,int r ,int l1,int r1,int vv,int ind){
    if(l1<=l&&r<=r1) {
        lal2[ind]=max(lal2[ind],vv);
        mxr[ind]=max(mxr[ind],vv);
        return;
    }
    int mid=l+r>>1;
    if(lal2[ind]!=-lar){
        int p=lal2[ind];lal2[ind]=-lar;
        lal2[ind*2]=max(lal2[ind*2],p);
        lal2[ind*2+1]=max(lal2[ind*2+1],p);mxr[ind*2]=max(mxr[ind*2],p);
        mxr[ind*2+1]=max(mxr[ind*2+1],p);
    }
    if(r1<=mid) upd2(l,mid,l1,r1,vv,ind*2);
    else if(l1>mid) upd2(mid+1,r,l1,r1,vv,ind*2+1);
    else{
        upd2(l,mid,l1,r1,vv,ind*2);upd2(mid+1,r,l1,r1,vv,ind*2+1);
    }
    mxr[ind]=max(mxr[ind*2],mxr[ind*2+1]);
}

int val1(int l,int r,int l1,int r1,int ind){
    if(l1<=l&&r<=r1) return mxl[ind];
    int mid=l+r>>1;
    if(lal1[ind]!=lar){
        int p=lal1[ind];lal1[ind]=lar;
        lal1[ind*2]=min(lal1[ind*2],p);
        lal1[ind*2+1]=min(lal1[ind*2+1],p);mxl[ind*2]=min(mxl[ind*2],p);
        mxl[ind*2+1]=min(mxl[ind*2+1],p);
    }
    if(r1<=mid) return val1(l,mid,l1,r1,ind*2);
    else if(l1>mid) return val1(mid+1,r,l1,r1,ind*2+1);
    else return  min(val1(l,mid,l1,r1,ind*2),val1(mid+1,r,l1,r1,ind*2+1));
    mxl[ind]=min(mxl[ind*2],mxl[ind*2+1]);
}

int val2(int l,int r,int l1,int r1,int ind){
    if(l1<=l&&r<=r1) return mxr[ind];
    int mid=l+r>>1;
    if(lal2[ind]!=-lar){
        int p=lal2[ind];lal2[ind]=-lar;
        lal2[ind*2]=max(lal2[ind*2],p);
        lal2[ind*2+1]=max(lal2[ind*2+1],p);mxr[ind*2]=max(mxr[ind*2],p);
        mxr[ind*2+1]=max(mxr[ind*2+1],p);
    }
    if(r1<=mid) return val2(l,mid,l1,r1,ind*2);
    else if(l1>mid) return val2(mid+1,r,l1,r1,ind*2+1);
    else return  max(val2(l,mid,l1,r1,ind*2),val2(mid+1,r,l1,r1,ind*2+1));
    mxr[ind]=max(mxr[ind*2],mxr[ind*2+1]);
}



void solve()
{
    int n,k;
    cin>>n>>k;
    rep(i,4*n){
        lal1[i]=lar,lal2[i]=-lar;
    }
    build(1,n,1);
    int m;
    cin>>m;
    rep(i,m){
        int g,h;
        cin>>g>>h;
        if(g<=h){
            upd2(1,n,g,min(g+k-1,h),h,1);
        }
        else{
            upd1(1,n,max(g-k+1,h),g,h,1);
        }
    }
    int q;
    cin>>q;
    rep(i,q){
        int g,h;
        cin>>g>>h;
        int l=g,r=g;
        int tt=0;
        while(h<l||h>r){
            tt++;
            int g1=l,g2=r;
            l=val1(1,n,g1,g2,1);
            r=val2(1,n,g1,g2,1);
            if(l==g1&&r==g2) break;
        }
        if(h<l||h>r) cout<<-1<<"\n";
        else cout<<tt<<"\n";
    }
}

signed main()
{
    IO
    solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void build(long long int, long long int, long long int)':
Main.cpp:39:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     int mid=l+r>>1;
      |             ~^~
Main.cpp: In function 'void upd1(long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:51:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     int mid=l+r>>1;
      |             ~^~
Main.cpp: In function 'void upd2(long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:72:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |     int mid=l+r>>1;
      |             ~^~
Main.cpp: In function 'long long int val1(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:89:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |     int mid=l+r>>1;
      |             ~^~
Main.cpp: In function 'long long int val2(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:104:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |     int mid=l+r>>1;
      |             ~^~

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