Submission #563514

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
563514	2022-05-17T11:34:58 Z	amunduzbaev	Railway Trip (JOI17_railway_trip)	C++17	100 / 100	428 ms	122212 KB

railway_trip

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

const int N = 2e5 + 5;
const int inf = N;
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;
		if(!u) sz[u] = N * 2;
		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 1;
		//~ 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";
		//~ cout<<v1<<" "<<v2<<" "<<p[v1]<<" "<<p[v2]<<"\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<<res<<"\n";
		//~ 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";
	}
}

/*

10 10 1
10 1 10 2 10 3 9 4 10 10 
1 10

*/

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	9812 KB	Output is correct
2	Correct	5 ms	9812 KB	Output is correct
3	Correct	6 ms	9812 KB	Output is correct
4	Correct	5 ms	9812 KB	Output is correct
5	Correct	5 ms	9812 KB	Output is correct
6	Correct	6 ms	9812 KB	Output is correct
7	Correct	5 ms	9812 KB	Output is correct
8	Correct	5 ms	9812 KB	Output is correct
9	Correct	5 ms	9684 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	10708 KB	Output is correct
2	Correct	93 ms	91824 KB	Output is correct
3	Correct	100 ms	97312 KB	Output is correct
4	Correct	107 ms	101176 KB	Output is correct
5	Correct	105 ms	102872 KB	Output is correct
6	Correct	108 ms	104992 KB	Output is correct
7	Correct	128 ms	106876 KB	Output is correct
8	Correct	54 ms	60512 KB	Output is correct
9	Correct	103 ms	82048 KB	Output is correct
10	Correct	85 ms	73576 KB	Output is correct
11	Correct	109 ms	82412 KB	Output is correct
12	Correct	103 ms	82320 KB	Output is correct
13	Correct	103 ms	81920 KB	Output is correct
14	Correct	107 ms	82516 KB	Output is correct
15	Correct	115 ms	82312 KB	Output is correct
16	Correct	104 ms	82200 KB	Output is correct
17	Correct	111 ms	105464 KB	Output is correct
18	Correct	116 ms	105520 KB	Output is correct
19	Correct	113 ms	108024 KB	Output is correct

Subtask #3

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	208 ms	95044 KB	Output is correct
2	Correct	217 ms	93896 KB	Output is correct
3	Correct	217 ms	96976 KB	Output is correct
4	Correct	219 ms	97356 KB	Output is correct
5	Correct	213 ms	97772 KB	Output is correct
6	Correct	212 ms	98552 KB	Output is correct
7	Correct	221 ms	98760 KB	Output is correct
8	Correct	176 ms	73240 KB	Output is correct
9	Correct	140 ms	62260 KB	Output is correct
10	Correct	141 ms	62280 KB	Output is correct
11	Correct	152 ms	62304 KB	Output is correct
12	Correct	145 ms	62296 KB	Output is correct
13	Correct	156 ms	62284 KB	Output is correct
14	Correct	150 ms	62408 KB	Output is correct
15	Correct	152 ms	63476 KB	Output is correct
16	Correct	181 ms	71180 KB	Output is correct

Subtask #4

55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	248 ms	106816 KB	Output is correct
2	Correct	252 ms	106772 KB	Output is correct
3	Correct	227 ms	105392 KB	Output is correct
4	Correct	259 ms	107432 KB	Output is correct
5	Correct	144 ms	62336 KB	Output is correct
6	Correct	270 ms	83712 KB	Output is correct
7	Correct	277 ms	83736 KB	Output is correct
8	Correct	226 ms	75316 KB	Output is correct
9	Correct	267 ms	84132 KB	Output is correct
10	Correct	276 ms	83936 KB	Output is correct
11	Correct	270 ms	83584 KB	Output is correct
12	Correct	273 ms	84044 KB	Output is correct
13	Correct	262 ms	83916 KB	Output is correct
14	Correct	352 ms	102616 KB	Output is correct
15	Correct	349 ms	110084 KB	Output is correct
16	Correct	428 ms	122212 KB	Output is correct
17	Correct	300 ms	94428 KB	Output is correct
18	Correct	349 ms	95260 KB	Output is correct
19	Correct	354 ms	95340 KB	Output is correct
20	Correct	306 ms	90856 KB	Output is correct
21	Correct	251 ms	106956 KB	Output is correct
22	Correct	240 ms	106940 KB	Output is correct
23	Correct	281 ms	109540 KB	Output is correct