Submission #116519

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

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]];
    }

    while(q--){
	pii A,B; cin>>A.F>>B.F; A.S=--A.F, B.S=--B.F;
	if(A.F>B.F) swap(A,B);
	int ans=0;
	while(max(A.F,B.F)>min(A.S,B.S)){
	    int numa= max(a[A.F],a[A.S]), numb= max(a[B.F],a[B.S]);
	    if(numa>numb) swap(A,B);
	    ans++;
	    if(a[A.F]<a[A.S]) A={bef[A.S],aft[A.S]};
	    else if(a[A.F]>a[A.S]) A={bef[A.F],aft[A.F]};
	    else A={bef[A.F],aft[A.S]};
	}
	cout<<ans-1<<"\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