Submission #691317

#	Time	Username	Problem	Language	Result	Execution time	Memory
691317		amunduzbaev	Railway Trip (JOI17_railway_trip)	C++17	25 / 100	2076 ms	79872 KiB

railway_trip

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

#define ar array
typedef long long ll;
//~ #define int ll

const int N = 2e5 + 5;
const int K = 20;
vector<int> edges[N];
int a[N], L[N], R[N], pos[N][K];
ar<int, 2> l[N][K], r[N][K];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, k, q; cin >> n >> k >> q;
	vector<int> ss;
	memset(L, -1, sizeof L);
	memset(R, -1, sizeof R);
	for(int i=0;i<n;i++){
		cin >> a[i]; a[i]--;
		while(!ss.empty() && a[ss.back()] < a[i]){
			ss.pop_back();
		}
		if(!ss.empty()){
			L[i] = ss.back();
		}
		ss.push_back(i);
	}
	ss.clear();
	for(int i=n-1;~i;i--){
		while(!ss.empty() && a[ss.back()] < a[i]){
			ss.pop_back();
		}
		if(!ss.empty()){
			R[i] = ss.back();
		}
		ss.push_back(i);
	}
	
	memset(l, 63, sizeof l);
	memset(r, 63, sizeof r);
	for(int i=0;i<n;i++){
		l[i][0] = r[i][0] = {i, 0};
		pos[i][0] = i;
	}
	for(int j=1;j<k;j++){
		for(int i=0;i<n;i++){
			auto [p, c] = l[i][j-1];
			if(a[p] >= j) l[i][j] = {p, c};
			else if(i != p) l[i][j] = {l[p][j][0], l[p][j][1] + c};
			else if(~L[i]){
				l[i][j] = l[L[i]][j]; l[i][j][1]++;
			} else assert(false);
		}
		
		for(int i=n-1;~i;i--){
			auto [p, c] = r[i][j-1];
			if(a[p] >= j) r[i][j] = {p, c};
			else if(i != p) r[i][j] = {r[p][j][0], r[p][j][1] + c};
			else if(~R[i]){
				r[i][j] = r[R[i]][j]; r[i][j][1]++;
			} else assert(false);
		}
		for(int i=0;i<n;i++){
			l[i][j][1] = min(l[i][j][1], l[r[i][j-1][0]][j][1] + r[i][j-1][1] + (a[r[i][j-1][0]] >= j));
			r[i][j][1] = min(r[i][j][1], r[l[i][j-1][0]][j][1] + l[i][j-1][1] + (a[l[i][j-1][0]] >= j));
		}
		
		int last = 0;
		for(int i=0;i<n;i++){
			if(a[i] >= j) pos[i][j] = last++;
		}
	}
	
	//~ for(int j=0;j<k;j++){
		//~ for(int i=0;i<n;i++){
			//~ cout<<l[i][j][0]<<" ";
		//~ } cout<<"\n";
	//~ } cout<<"\n";
	//~ for(int j=0;j<k;j++){
		//~ for(int i=0;i<n;i++){
			//~ cout<<l[i][j][1]<<" ";
		//~ } cout<<"\n";
	//~ } cout<<"\n";
	//~ for(int j=0;j<k;j++){
		//~ for(int i=0;i<n;i++){
			//~ cout<<r[i][j][0]<<" ";
		//~ } cout<<"\n";
	//~ } cout<<"\n";
	//~ for(int j=0;j<k;j++){
		//~ for(int i=0;i<n;i++){
			//~ cout<<r[i][j][1]<<" ";
		//~ } cout<<"\n";
	//~ } cout<<"\n";
	
	auto check = [&](int j, ar<int, 2> a, ar<int, 2> b){
		if(a[0] > n || b[0] > n) assert(false); 
		//~ cout<<j<<" "<<a[0]<<" "<<b[0]<<" "<<abs(pos[a[0]][j] - pos[b[0]][j])<<" "<<a[1] + b[1]<<"\n";
		return abs(pos[a[0]][j] - pos[b[0]][j]) + a[1] + b[1];
	};
	
	while(q--){
		int a, b; cin >> a >> b;
		a--, b--;
		int res = 1e9;
		for(int j=0;j<k;j++){
			res = min(res, check(j, l[a][j], l[b][j]));
			res = min(res, check(j, l[a][j], r[b][j]));
			res = min(res, check(j, r[a][j], l[b][j]));
			res = min(res, check(j, r[a][j], r[b][j]));
		}
		cout<<--res<<"\n";
	}
}

/*

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

*/

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