Submission #813277

#	Time	Username	Problem	Language	Result	Execution time	Memory
813277		sentheta	Railway Trip (JOI17_railway_trip)	C++17	100 / 100	236 ms	77544 KiB

railway_trip

// author : sentheta aka vanwij
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
	#define DBG 0
#else
	#include"bits/stdc++.h"
	#define DBG 0
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)

#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}

#define int long long
// const Int MOD = 1e9+7;
const Int MOD = 998244353;
Int bpow(Int a,Int b){
	Int ret = 1;
	for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD;
	return ret;
}
Int inv(Int a){return bpow(a,MOD-2);}

void solve(); int TC, ALLTC;
signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed << setprecision(7);
	// cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0;
	solve();
}










const int N = 1e5+5;
const int LN = 17;

int n, k, q;

int a[N];
V<int> bya[N];

struct Stable{
	int st[N][LN];
	void build(){
		rep(i,0,N) st[i][0] = a[i];
		rep(lg,1,LN) for(int i=0; i+(1<<lg)-1<N; i++){
			st[i][lg] = max(st[i][lg-1], st[i+(1<<(lg-1))][lg-1]);
		}
	}
	int qry(int l,int r){
		int lg = __lg(r-l+1);
		return max(st[l][lg], st[r-(1<<lg)+1][lg]);
	}
} stable;

V<int> adj[N];

int prv[N][LN], nxt[N][LN];

int pl[N][LN];
int pr[N][LN];

void solve1(){
	int s, t;
	cin >> s >> t;
	// wlog s < t
	if(!(s<t)) swap(s,t);
	
	int ans = 0;
	
	dbg(s);
	int sl=s, sr=s;
	int tl=t, tr=t;
	for(int b=LN-1; b>=0; b--){
		int nsl = min(pl[sl][b], pl[sr][b]);
		int nsr = max(pr[sl][b], pr[sr][b]);
		if(nsr < tl){
			ans += 1<<b;
			sl = nsl; sr = nsr;
		}
		
		int ntl = min(pl[tl][b], pl[tr][b]);
		int ntr = max(pr[tl][b], pr[tr][b]);
		if(sr < ntl){
			ans += 1<<b;
			tl = ntl; tr = ntr;
		}
	}
	dbg(sl); dbg(sr);
	dbg(ans);
	cerr << nl;

	dbg(tl); dbg(tr);
	dbg(ans);
	cerr << nl;
	
	ans++;
		
	cout << ans-1 << nl;
}

void solve(){
	
	cin >> n >> k >> q;
	
	rep(i,1,n+1){
		cin >> a[i];
		bya[a[i]].push_back(i);
	}
	stable.build();
	
	// toward-left edges
	V<int> stak;
	rep(i,1,n+1){
		while(!stak.empty() && a[stak.back()]<a[i]) stak.pop_back();
		if(stak.empty()) stak.push_back(i);

		int j = stak.back();
		prv[i][0] = j;
		pl[i][0] = j;
		// adj[i].push_back(j);
		// adj[j].push_back(i);
		
		if(stak.back()!=i) stak.push_back(i);
	}
	
	// toward-right edges
	stak.clear();
	for(int i=n; i>=1; i--){
		while(!stak.empty() && a[stak.back()]<a[i]) stak.pop_back();
		if(stak.empty()) stak.push_back(i);
		
		int j = stak.back();
		nxt[i][0] = j;
		pr[i][0] = j;
		// adj[i].push_back(j);
		// adj[j].push_back(i);
		
		if(stak.back()!=i) stak.push_back(i);
	}
	
	// build p[][]
	rep(lg,1,LN) rep(i,1,n+1){
		prv[i][lg] = prv[prv[i][lg-1]][lg-1];
		nxt[i][lg] = nxt[nxt[i][lg-1]][lg-1];
		
		
		pl[i][lg] = min({
			pl[pl[i][lg-1]][lg-1], pl[pr[i][lg-1]][lg-1]
		});
		pr[i][lg] = max({
			pr[pl[i][lg-1]][lg-1], pr[pr[i][lg-1]][lg-1]
		});
		
	}
	
	
	while(q--){
		solve1();
	}
	
	
}

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