Submission #827765

#	Time	Username	Problem	Language	Result	Execution time	Memory
827765		winter0101	Railway Trip 2 (JOI22_ho_t4)	C++14	100 / 100	1136 ms	284604 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define eb emplace_back
#define pli pair<long long,int>
const int maxn=1e5+9;
struct line{
int l,r;
}a[maxn*2];
pii b[maxn],jump[maxn][18];
int minl[maxn][18][18],maxr[maxn][18][18];
vector<int>add[maxn],del[maxn];
int lg[maxn];
int get1(int l,int r,int k){
int dis=lg[r-l+1];
return min(minl[l][dis][k],minl[r-(1<<dis)+1][dis][k]);
}
int get2(int l,int r,int k){
int dis=lg[r-l+1];
return max(maxr[l][dis][k],maxr[r-(1<<dis)+1][dis][k]);
}
bool checkinside(int l,int r,int x){
return (l<=x&&x<=r);
}
int n,k,m;
void buildleft(){
    for1(i,1,n)b[i]={i,i};
    for1(i,1,m){
    if (a[i].l>a[i].r){
        add[a[i].l].pb(a[i].r);
        del[max(a[i].l-k+1,a[i].r+1)].pb(a[i].r);
        //cerr<<a[i].l<<" "<<min(a[i].l-k+1,a[i].r+1)<<'\n';
    }
    }
    multiset<int>ss;
    for2(i,n,1){
    for (auto v:add[i]){
        ss.insert(v);
    }
    if (!ss.empty())b[i].fi=*ss.begin();
    for (auto v:del[i]){
        ss.erase(ss.find(v));
    }
    vector<int>().swap(add[i]);
    vector<int>().swap(del[i]);
    }
}
void buildright(){
    for1(i,1,m){
    if (a[i].l<a[i].r){
        add[a[i].l].pb(a[i].r);
        del[min(a[i].l+k-1,a[i].r-1)].pb(a[i].r);
    }
    }
    multiset<int>ss;
    for1(i,1,n){
    for (auto v:add[i]){
        ss.insert(v);
    }
    if (!ss.empty()){
        auto it=ss.end();
        it--;
        b[i].se=*it;
    }
    for (auto v:del[i]){
        ss.erase(ss.find(v));
    }
    vector<int>().swap(add[i]);
    vector<int>().swap(del[i]);
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n>>k>>m;
    for1(i,2,n)lg[i]=lg[i/2]+1;
    for1(i,1,m){
    cin>>a[i].l>>a[i].r;
    }
    buildleft();
    buildright();
    //cout<<b[3].fi<<" "<<b[3].se<<'\n';
    //return 0;
    for1(i,1,n){
    jump[i][0]=b[i];
    }
    for1(j,1,18){
    for1(i,1,n){
    minl[i][0][j-1]=jump[i][j-1].fi;
    maxr[i][0][j-1]=jump[i][j-1].se;
    }
    for1(l,1,17){
    for1(i,1,n-(1<<l)+1){
    minl[i][l][j-1]=min(minl[i][l-1][j-1],minl[i+(1<<(l-1))][l-1][j-1]);
    maxr[i][l][j-1]=max(maxr[i][l-1][j-1],maxr[i+(1<<(l-1))][l-1][j-1]);
    }
    }
    if (j==18)break;
    for1(i,1,n){
    int l1=jump[i][j-1].fi,r1=jump[i][j-1].se;
    int newl1=min(l1,get1(l1,r1,j-1)),newr1=max(r1,get2(l1,r1,j-1));
    jump[i][j]={newl1,newr1};
    }
    }
    int q;
    cin>>q;
    for1(i,1,q){
    int s,t;
    cin>>s>>t;
    if (s==t){
        cout<<0<<'\n';
        continue;
    }
    int ans=0;
    pii nw={s,s};
    for2(j,17,0){
    int l1=nw.fi,r1=nw.se;
    int newl1=min(l1,get1(l1,r1,j)),newr1=max(r1,get2(l1,r1,j));
    //cerr<<j<<" "<<l1<<" "<<r1<<" "<<newl1<<" "<<newr1<<'\n';
    if (!checkinside(newl1,newr1,t)){
        //cerr<<j<<'\n';
        ans+=(1<<j);
        nw.fi=newl1;
        nw.se=newr1;
    }
    }
    //cout<<nw.fi<<" "<<nw.se<<'\n';
    for2(j,0,0){
    int l1=nw.fi,r1=nw.se;
    int newl1=min(l1,get1(l1,r1,j)),newr1=max(r1,get2(l1,r1,j));
    if (!checkinside(newl1,newr1,t)){
        cout<<-1<<'\n';
    }
    else cout<<ans+1<<'\n';
    }
    }
    //cout<<jump[3][1].fi<<" "<<jump[3][1].se<<'\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