Submission #340986

#	Time	Username	Problem	Language	Result	Execution time	Memory
340986		mehrdad_sohrabi	Railway Trip (JOI17_railway_trip)	C++14	100 / 100	300 ms	43748 KiB

railway_trip

#include <bits/stdc++.h>
/// 500 485
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=1e5+100,M=20;
int nxtl[N][M];
int nxtr[N][M];
ll a[N];
vector <int> ja[N];
ll seg[N*4];
void build(ll nod,ll l,ll r){
    if (r-l==1){
        seg[nod]=a[l];
        return ;
    }
    ll mid=(r+l)/2;
    build(nod*2,l,mid);
    build(nod*2+1,mid,r);
    seg[nod]=max(seg[nod*2],seg[nod*2+1]);
}
ll get(ll nod,ll l,ll r,ll L,ll R){
    if (l>=R || L>=r) return 0;
    if (l>=L && r<=R){
        return seg[nod];
    }
    ll mid=(r+l)/2;
    return max(get(nod*2,l,mid,L,R),get(nod*2+1,mid,r,L,R));
}
ll num(ll l,ll r,ll x){
    if (l>r) swap(l,r);
    ll z=upper_bound(ja[x].begin(),ja[x].end(),r)-ja[x].begin();
    ll t=lower_bound(ja[x].begin(),ja[x].end(),l)-ja[x].begin();
    return z-t;
}
int L[N],R[N];
int32_t main(){
    sync;
    ll n,k,q;
    cin >> n >> k >> q ;
    for (int i=1;i<=n;i++){
        cin >> a[i];
        ja[a[i]].pb(i);
    }
    build(1,1,n+1);
    vector <int> agh;
    agh.pb(0);
    a[0]=N-1;
    for (int i=1;i<=n;i++){
        while(agh.size() && a[agh.back()]<a[i]) agh.pop_back();
        L[i]=agh.back();
        agh.pb(i);
    }
    agh.clear();
    agh.pb(n+1);
    a[n+1]=N-1;
    for (int i=n;i;i--){
        while(agh.size() && a[agh.back()]<a[i]) agh.pop_back();
        R[i]=agh.back();
        agh.pb(i);
    }
    for (int i=N-1;i;i--){
        for (auto u : ja[i]){
            nxtl[u][0]=L[u];
            nxtr[u][0]=R[u];
        }
    }
    for (int i=0;i<M;i++){
        nxtl[0][i]=0;
        nxtr[0][i]=0;
        nxtl[n+1][i]=n+1;
        nxtr[n+1][i]=n+1;
    }
    for (int j=1;j<M;j++){
        for (int i=1;i<=n;i++){
            nxtl[i][j]=min(nxtl[nxtl[i][j-1]][j-1],nxtl[nxtr[i][j-1]][j-1]);
            nxtr[i][j]=max(nxtr[nxtr[i][j-1]][j-1],nxtr[nxtl[i][j-1]][j-1]);
        }
    }
    while(q--){
        ll x,y;
        cin >> x >> y;
        if (x>y) swap(x,y);
        if (x+1==y){
            cout << 0 << endl;
            continue;
        }
        /*
        ll z=get(1,1,n+1,x+1,y);
        if (z<min(a[x],a[y])){
            cout << 0 << endl;
            continue;
        }
        */
        ll l=x,r=x;
        ll ans=0;
        for (int i=M-1;i>-1;i--){
            ll newl=l,newr=r;
            newl=min(nxtl[l][i],nxtl[r][i]);
            newr=max(nxtr[l][i],nxtr[r][i]);
            if (newr<y){
                l=newl;
                r=newr;
                ans+=(1<<i);
            }
        }
        //cout << l << " " << r << " " << ans << endl;
        ll L=y,R=y;
        for (int i=M-1;i>-1;i--){
            ll newl=L,newr=R;
            newl=min(nxtl[L][i],nxtl[R][i]);
            newr=max(nxtr[L][i],nxtr[R][i]);
            if (newl>r){
                L=newl;
                R=newr;
                ans+=(1<<i);
            }
        }
        cout << ans<< endl;
    }

}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55