Submission #563500

#	Time	Username	Problem	Language	Result	Execution time	Memory
563500		amunduzbaev	Railway Trip (JOI17_railway_trip)	C++17	5 / 100	205 ms	220508 KiB

railway_trip

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define int long long

const int N = 1e5 + 5;
const int inf = 1e9 + 7;
vector<int> edges[N], pos[N];
int a[N], par[N][20], path[N][20][2][2], p[N];
int st[N][20], tin[N], tout[N], t;
int L[N], R[N], ver[N], sz[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, k, q; cin>>n>>k>>q;
	for(int i=0;i<n;i++){
		cin>>a[i];
		st[i][0] = a[i];
		pos[a[i]].push_back(i);
	}
	
	for(int j=1;j<20;j++){
		for(int i=0;i+(1 << (j - 1)) < n;i++){
			st[i][j] = max(st[i][j-1], st[i + (1 << (j - 1))][j-1]);
		}
	}
	
	auto ger = [&](int l, int r){
		int lg = __lg(r - l + 1);
		return max(st[l][lg], st[r - (1 << lg) + 1][lg]);
	};
	
	int last = 1;
	function<void(int, int, int)> get = [&](int l, int r, int u){
		//~ cout<<l<<" "<<r<<" "<<u<<"\n";
		tin[u] = ++t;
		for(int j=1;j<20;j++){
			par[u][j] = par[par[u][j-1]][j-1];
			//~ if(par[u][j-1]){
				//~ cout<<par[u][j-1]<<" "<<par[par[u][j-1]][j-1]<<"\n";
			//~ }
			for(int t=0;t<2;t++){
				for(int k=0;k<2;k++){
					if(u) path[u][j][t][k] = inf;
					for(int l=0;l<2;l++){
						path[u][j][t][k] = min(path[u][j][t][k], path[u][j-1][t][l] + path[par[u][j-1]][j-1][l][k]);
					}
				}
			}
		}
		if(l + 1 >= r){
			tout[u] = t;
			return;
		}
		
		int mx = ger(l + 1, r - 1);
		int i = upper_bound(pos[mx].begin(), pos[mx].end(), l) - pos[mx].begin();
		int lx = l, P = 0;
		for(;i<(int)pos[mx].size() && pos[mx][i] < r;i++){
			int j = pos[mx][i];
			ver[j] = last;
			edges[u].push_back(last);
			p[last] = P++;
			L[last] = lx, R[last] = j;
			last++, lx = j;
		}
		
		edges[u].push_back(last);
		p[last] = P++;
		sz[u] = P, L[last] = lx, R[last] = r;
		last++;
		for(auto x : edges[u]){
			par[x][0] = u;
			path[x][0][0][0] = min(p[x], sz[u] - p[x] + 1);
			path[x][0][1][1] = min(p[x] + 2, sz[u] - p[x] - 1);
			path[x][0][0][1] = path[x][0][1][0] = min(p[x] + 1, sz[u] - p[x]);
			get(L[x], R[x], x);
		}
		tout[u] = t;
	};
	get(-1, n, 0);
	//~ for(int i=1;i<last;i++){
		//~ for(int j=0;j<3;j++){
			//~ cout<<par[i][j]<<" ";
		//~ } cout<<"\n";
	//~ }
	
	auto is = [&](int a, int b){
		return (tin[a] <= tin[b] && tin[b] <= tout[a]);
	};
	
	auto gg = [&](ar<int, 2>& d, int a, int b){
		for(int j=19;~j;j--){
			if(!is(par[b][j], a)){
				ar<int, 2> T {};
				//~ cout<<d[0]<<" "<<d[1]<<" "<<par[b][j]<<"\n";
				T[0] = min(d[0] + path[b][j][0][0], d[1] + path[b][j][1][0]);
				T[1] = min(d[0] + path[b][j][0][1], d[1] + path[b][j][1][1]);
				swap(T, d);
				b = par[b][j];
			}
		}
		
		return b;
	};
	
	//~ cout<<ver[0]<<"\n";
	
	auto check = [&](int a, int ta, int b, int tb){
		int res = inf;
		if(a == b) return 1ll;
		//~ cout<<a<<" "<<b<<"\n";
		if(is(b, a)) swap(a, b), swap(tb, ta);
		if(is(a, b)){
			ar<int, 2> d {}; d[!tb]++;
			int v = gg(d, a, b);
			//~ cout<<d[0]<<" "<<d[1]<<" <-\n";
			ar<int, 2> T {};
			T[0] = min(d[0] + path[v][0][0][0], d[1] + path[v][0][1][0]);
			T[1] = min(d[0] + path[v][0][0][1], d[1] + path[v][0][1][1]);
			return T[ta];
		}
		//~ cout<<a<<" "<<b<<"\n";
		ar<int, 2> d1 {}, d2 {};
		d1[!ta]++; d2[!tb]++;
		int v1 = gg(d1, b, a);
		int v2 = gg(d2, a, b);
		
		//~ cout<<d1[0]<<" "<<d1[1]<<"\n";
		//~ cout<<d2[0]<<" "<<d2[1]<<"\n";
		
		for(int t=0;t<2;t++){
			for(int k=0;k<2;k++){
				int bet = abs(p[v1] + t - p[v2] - k);
				bet = min({bet, path[v1][0][t][0] + path[v2][0][k][0], path[v1][0][t][1] + path[v2][0][k][1]});
				//~ cout<<t<<" "<<k<<" "<<d1[t]<<" "<<d2[k]<<" "<<bet<<"\n";
				res = min(res, d1[t] + d2[k] + bet);
			}
		}
		//~ cout<<"\n";
		
		return res;
	};
	
	while(q--){
		int i, j; cin>>i>>j;
		i--, j--;
		int res = inf;
		for(int t=0;t<2;t++){
			for(int k=0;k<2;k++){
				//~ int x = check(ver[i] + t, !t, ver[j] + k, !k);
				//~ cout<<x<<"\n";
				//~ res = min(res, x);
				res = min(res, check(ver[i] + t, !t, ver[j] + k, !k));
				//~ cout<<check(ver[i] + t, !t, ver[j] + k, !k)<<"\n";
			}
		}
		
		cout<<res - 1<<"\n";
		//~ cout<<"\n";
	}
}

/*

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
5 4 1 2 3 1 1 2 4 5 4  1  5  3  5

15 5 2
5
4
1
2
3
1
1
2
4
5
4
1
5
3
5
8 1
5 3

2
1

*/

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