Submission #116527

#	Time	Username	Problem	Language	Result	Execution time	Memory
116527		shayan_p	Railway Trip (JOI17_railway_trip)	C++14	100 / 100	374 ms	19664 KiB

railway_trip

// High above the clouds there is a rainbow...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=1e5+10;

int a[maxn],bef[maxn],aft[maxn],n;
pii sp[20][maxn];

pii NXT(pii p,int i){
    pii ans;
    ans.F= min( sp[i][p.F].F, sp[i][p.S].F );
    ans.S= max( sp[i][p.F].S, sp[i][p.S].S );
    return ans;
}

pair<int,pii> f(int pos,int l,int r){
    pair<int,pii> ans={0,{pos,pos}};
    for(int i=19;i>=0;i--){
	pii p=NXT(ans.S,i);
	if(l<p.F && p.S<r) ans.F+=(1<<i), ans.S=p;
    }
    return ans;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);

    int k,q;cin>>n>>k>>q;

    for(int i=0;i<n;i++){
	cin>>a[i], --a[i];
	a[i]=min(a[i],k-1);
    }
    
    for(int i=0;i<n;i++){
	bef[i]=i-1;
	while(bef[i]>=0 && a[bef[i]]<a[i])
	    bef[i]=bef[bef[i]];
    }
    for(int i=n-1;i>=0;i--){
	aft[i]=i+1;
	while(aft[i]<n && a[aft[i]]<a[i])
	    aft[i]=aft[aft[i]];
    }
    bef[0]=0, aft[n-1]=n-1;
    
    for(int i=0;i<n;i++){
	sp[0][i]={bef[i],aft[i]};
    }
    for(int i=1;i<20;i++){
	for(int j=0;j<n;j++){
	    sp[i][j]= NXT(sp[i-1][j],i-1);
	}
    }
    
    while(q--){
	int A,B; cin>>A>>B; --A,--B;
	if(A>B) swap(A,B);
	pair<int,pii> aa=f(A,-1,B);
	pair<int,pii> bb=f(B,aa.S.S,n);
	cout<<aa.F+bb.F<<"\n";
    }
    return 0;
}
// Deathly mistakes:
//  * Read the problem curfully.
//  * Check maxn.
//  * Overflows.

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