Submission #116525

#	Time	Username	Problem	Language	Result	Execution time	Memory
116525		shayan_p	Railway Trip (JOI17_railway_trip)	C++14	20 / 100	2039 ms	2288 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;

pair<int,pii> f(int pos,int l,int r){
    int L=pos,R=pos,ans=0;
    while(1){
	int LL,RR;
	if(a[L]<a[R]) LL=bef[R],RR=aft[R];
	else if(a[L]>a[R]) RR=aft[L],LL=bef[L];
	else LL=bef[L],RR=aft[R];
	if(l<LL && RR<r) L=LL,R=RR,ans++;
	else break;
    }
    return {ans,{L,R}};
}

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;
    
    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: 0 / 25
• Subtask 4: 0 / 55