Submission #815471

#	Time	Username	Problem	Language	Result	Execution time	Memory
815471		sentheta	Railway Trip (JOI17_railway_trip)	C++17	0 / 100	281 ms	74644 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];

// p[i][k] = maximum value after 2^k moves, leftmost and rightmost position
int pl[N][LN], pr[N][LN];

void solve1(){
	int s, t;
	cin >> s >> t;
	// wlog s < t
	if(!(s<t)) swap(s,t);
	if(s==t-1){
		cout << 0 << nl; return;
	}
	int ans = N;
	dbg(s); dbg(t);
	
	int barrier = stable.qry(s+1,t-1);
	dbg(barrier);
	
	int sl=s, sr=s;
	int tl=t, tr=t;
	int dist = 0;
	for(int b=LN-1; b>=0; b--){
		if(sl!=pl[sl][b] && sr!=pr[sr][b] && a[pl[sl][b]]<barrier){
			sl = pl[sl][b]; sr = pr[sr][b];
			dist += 1<<b;
		}
		if(tl!=pl[tl][b] && tr!=pr[tr][b] && a[pl[tl][b]]<barrier){
			tl = pl[tl][b]; tr = pr[tr][b];
			dist += 1<<b;
		}
	}
	dbg(sl); dbg(sr); dbg(tl); dbg(tr);
	assert(sr < tl);
	
	int dsl=1, dsr=1, dtl=1, dtr=1;
	for(int b=LN-1; b>=0; b--){
		if(a[prv[sl][b]]<barrier) sl=prv[sl][b], dsl+=1<<b;
		if(a[nxt[sr][b]]<barrier) sr=nxt[sr][b], dsr+=1<<b;
		if(a[prv[tl][b]]<barrier) tl=prv[tl][b], dtl+=1<<b;
		if(a[nxt[tr][b]]<barrier) tr=nxt[tr][b], dtr+=1<<b;
	}
	sl=prv[sl][0];
	sr=nxt[sr][0];
	tl=prv[tl][0];
	tr=nxt[tr][0];
	
	
	V<pii> vs = {
		{s,0}, {sl,dsl}, {sr,dsr}
	};
	V<pii> vt = {
		{t,0}, {tl,dtl}, {tr,dtr}
	};
	
	dbg(dist);
	for(auto[ox,dx] : vs) cerr << ox << " ";
	cerr << nl;
	for(auto[oy,dy] : vt) cerr << oy << " ";
	cerr << nl;
	
	
	for(auto[ox,dx] : vs) if(a[ox] >= barrier)
	for(auto[oy,dy] : vt) if(a[oy] >= barrier){
		cerr << nl;
		int x=ox, y=oy;
		dbg(x); dbg(y);
		
		int dist2 = dist + dx + dy;
		// if(x!=s) dist2++;
		// if(y!=t) dist2++;
		dbg(dist2);
		
		// move x to y
		if(a[x] <= a[y]){
			if(x < y){
				for(int b=LN-1; b>=0; b--){
					if(nxt[x][b] < y){
						x = nxt[x][b];
						dist2 += 1<<b;
					}
				}
			}
			else if(y < x){
				for(int b=LN-1; b>=0; b--){
					if(y < prv[x][b]){
						x = prv[x][b];
						dist2 += 1<<b;
					}
				}
			}
			if(x!=y){
				dist2++;
				if(x < y) x = nxt[x][0];
				else x = prv[x][0];
			}
		}
		
		// y move left to x
		else{
			if(x < y){
				for(int b=LN-1; b>=0; b--){
					if(x < prv[y][b]){
						y = prv[y][b];
						dist2 += 1<<b;
					}
				}
			}
			else if(y < x){
				for(int b=LN-1; b>=0; b--){
					if(nxt[y][b] < x){
						y = nxt[y][b];
						dist2 += 1<<b;
					}
				}
			}
			if(x!=y){
				dist2++;
				if(x < y) y = prv[y][0];
				else y = nxt[y][0];
			}
		}
		
		assert(x==y);
		ans = min(ans, dist2);
		dbg(dist2);
	}
	
	
	assert(ans < N);
	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;
		
		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;
		
		if(stak.back()!=i) stak.push_back(i);
	}
	
	// build p[][]
	rep(i,1,n+1){
		int mx = max({
			a[prv[i][0]], a[nxt[i][0]]
		});
		
		pl[i][0] = N;
		pr[i][0] = 0;
		if(a[prv[i][0]]==mx){
			pl[i][0] = min(pl[i][0], prv[i][0]);
			pr[i][0] = max(pr[i][0], prv[i][0]);
		}
		if(a[nxt[i][0]]==mx){
			pl[i][0] = min(pl[i][0], nxt[i][0]);
			pr[i][0] = max(pr[i][0], nxt[i][0]);
		}
		
		// dbg(i);
		// dbg(nxt[i][0]);
		// dbg(prv[i][0]);
		// dbg(pl[i][0]);
		// dbg(pr[i][0]);
		// cerr << nl;
	}
	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];
		
		V<int> v = {
			pl[pl[i][lg-1]][lg-1], pl[pr[i][lg-1]][lg-1],
			pr[pl[i][lg-1]][lg-1], pr[pr[i][lg-1]][lg-1]
		};
		int mx = 0;
		for(int j : v) mx = max(mx, a[j]);
		
		pl[i][lg] = N;
		pr[i][lg] = 0;
		for(int j : v) if(a[j]==mx){
			pl[i][lg] = min(pl[i][lg], j);
			pr[i][lg] = max(pr[i][lg], j);
		}
	}
	
	
	while(q--){
		solve1();
	}
	
	
}

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