Submission #415059

#	Time	Username	Problem	Language	Result	Execution time	Memory
415059		amoo_safar	Railway Trip (JOI17_railway_trip)	C++17	45 / 100	2084 ms	37316 KiB

railway_trip

// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 1e5 + 10;
const int Inf = N + N;
const ll Log = 30;

int n, k, q;
int a[N], sz[N];
int L[N], wL[N], l[N], szl[N];
int R[N], wR[N], r[N], szr[N];

typedef pair<int, int> pii;
typedef pair<int, int> T;
typedef pair<int, T> P;

P nxt(T A){
	pii lf = {wL[A.F], -a[L[A.F]]};
	pii rt = {wR[A.S], -a[R[A.S]]};
	if(lf == rt)
		return {lf.F, {L[A.F], R[A.S]} };
	if(lf < rt)
		return {lf.F, {L[A.F], L[A.F]} };
	return {rt.F, {R[A.S], R[A.S]}};
}

int Edge(int u, int v){
	if(u > v) swap(u, v);
	int res = Inf;
	if(R[u] > v)
		res = min(res, szl[v] - szl[u]);
	if(L[v] < u)
		res = min(res, szr[u] - szr[v]);
	if(res < 0){
		debug(res);
		cerr << "!! " << u << ' ' << v << '\n';
		cerr << "## " << szl[u] << ' ' << szl[v] << '\n'; 
		assert(false);
	}
	return res;
}
const int FN = 11;
int dp[FN][FN];
int Floyd(vector<int> V, vector<int> S, vector<int> T){
	int res = Inf;
	int _n = V.size();
	memset(dp, 31, sizeof dp);
	for(int i = 0; i < _n; i++)
		for(int j = 0; j < _n; j++)
			dp[i][j] = dp[j][i] = Edge(V[i], V[j]);
	for(int k = 0; k < _n; k++)
		for(int i = 0; i < _n; i++)
			for(int j = 0; j < _n; j++)
				dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k][j]);
	for(auto sr : S)
		for(auto ds : T)
			res = min(res, dp[sr][ds]);
	return res;
}


int sp[N+N][Log], po = 0;
int WW[N+N][Log];

map<T, int> mp;
// map<int, T> rv;
T rv[N + N];

int Calc(T A){
	if(mp.count(A))
		return mp[A];

	int i = po ++;
	rv[i] = A;
	mp[A] = i;
	if(A.F == 0 || A.S == n + 1){
		fill(sp[i], sp[i] + Log, i);
		fill(WW[i], WW[i] + Log, Inf);
		return i;
	}
	T B = nxt(A).S;
	int ww = nxt(A).F;
	int nx = Calc(B);
	sp[i][0] = nx;
	WW[i][0] = ww;
	for(int l = 1; l < Log; l++){
		sp[i][l] = sp[sp[i][l - 1]][l - 1];
		WW[i][l] = WW[i][l - 1] + WW[sp[i][l - 1]][l - 1];
	}
	return i;
}


int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k >> q;
	for(int i = 1; i <= n; i++) cin >> a[i];
	a[0] = a[n + 1] = k + 1;
	{ // stack
		vector<int> V = {0};
		for(int i = 1; i <= n; i++){
			while(a[V.back()] < a[i]) V.pop_back();
			l[i] = V.back();
			V.pb(i);
			sz[i] = V.size();
		}
		V = {0};
		for(int i = 1; i <= n; i++){
			while(a[V.back()] <= a[i]) V.pop_back();
			L[i] = V.back();
			V.pb(i);
		}
		sz[0] = 1; wL[0] = n; l[0] = L[0] = 0;
		for(int i = 1; i <= n; i++)
			wL[i] = L[i] != 0 ? sz[i] - sz[L[i]] : Inf;
		memcpy(szl, sz, sizeof sz);

		V = {n + 1};
		for(int i = n; i >= 1; i--){
			while(a[V.back()] < a[i]) V.pop_back();
			r[i] = V.back();
			V.pb(i);
			sz[i] = V.size();
		}
		V = {n + 1};
		for(int i = n; i >= 1; i--){
			while(a[V.back()] <= a[i]) V.pop_back();
			R[i] = V.back();
			V.pb(i);
		}
		sz[n + 1] = 1; wR[n + 1] = n; r[n + 1] = R[n + 1] = n + 1;
		for(int i = 1; i <= n; i++)
			wR[i] = R[i] != n + 1 ? sz[i] - sz[R[i]] : Inf;
		memcpy(szr, sz, sizeof sz);
	}
	// auto res = nxt({3, 3});
	// cerr << res.F << ' ' << res.S.F << ' ' << res.S.S << '\n';

	// debug(Edge(5, 1));
	// debug(R[1]);
	// exit(0);
	int src, des;
	for(int i = 0; i < q; i++){
		cin >> src >> des;
		if(src > des) swap(src, des);

		// int idx = max_element(a + src, a + des + 1) - a;
		// int mx = a[idx];
		int lx = src, rx = des;
		while(R[lx] <= des) lx = R[lx];
		while(src <= L[rx]) rx = L[rx];
		int mx = a[lx];

		// for(int j = src; j <= des; j++) if(a[j] == mx) rx = j;
		// for(int j = src; j <= des; j++) if(a[j] == mx){ lx = j; break; }
		
		pii s1 = {src, src};
		int id = Calc(s1);

		int res = 0;
		int cnt = 0;
		for(int l = Log - 1; l >= 0; l--){
			if(a[ rv[ sp[id][l] ].F ] >= mx) continue;
			res += WW[id][l];
			id = sp[id][l];
		}
		s1 = rv[id];
		// cerr << "!! " << s1.F << ' ' << s1.S << ' ' << rv[id].F << ' ' << rv[id].S << '\n';
		pii s2 = {des, des};
		id = Calc(s2);
		for(int l = Log - 1; l >= 0; l--){
			if(a[ rv[ sp[id][l] ].F ] >= mx) continue;
			res += WW[id][l];
			id = sp[id][l];
		}
		s2 = rv[id];
		// cerr << "$$ " << s2.F << ' ' << s2.S << ' ' << res << '\n';
		// debug(Edge(5, 1));
		// debug(Edge(1, 9));
		vector<int> nodes = {lx, rx, s1.F, s1.S, s2.F, s2.S};
		vector<int> S = {2, 3};
		vector<int> T = {4, 5};

		if(L[lx] != 0) nodes.pb(L[lx]);
		if(R[rx] != n + 1) nodes.pb(R[rx]);
		if(l[lx] != 0) nodes.pb(l[lx]);
		if(r[rx] != n + 1) nodes.pb(r[rx]);
		
		cout << res -1 + Floyd(nodes, S, T) << '\n';
	}
	return 0;
}
/*
9 3 3
3 1 1 1 2 2 2 3 3
2 4
4 9
6 7

*/

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