oj.uz

Submission #415062

# Submission time Handle Problem Language Result Execution time Memory
415062 2021-05-31T13:34:37 Z amoo_safar Railway Trip (JOI17_railway_trip) C++17
100 / 100
 1241 ms 61296 KB 
// 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 Rs[N][Log];
int Ls[N][Log];

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);
	Rs[n + 1][0] = n + 1;
	for(int i = 1; i <= n; i++)
		Rs[i][0] = R[i];
	Ls[0][0] = 0;
	for(int i = 1; i <= n; i++)
		Ls[i][0] = L[i];

	for(int l = 1; l < Log; l++)
		for(int i = 1; i <= n + 1; i++)
			Rs[i][l] = Rs[ Rs[i][l - 1] ][ l - 1 ];
	for(int l = 1; l < Log; l++)
		for(int i = 0; i <= n; i++)
			Ls[i][l] = Ls[ Ls[i][l - 1] ][ l - 1 ];

	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;
		for(int l = Log - 1; l >= 0; l--)
			if(Rs[lx][l] <= des)
				lx = Rs[lx][l];
		// while(R[lx] <= des) lx = R[lx];

		for(int l = Log - 1; l >= 0; l--)
			if(src <= Ls[rx][l])
				rx = Ls[rx][l];
		// 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.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1484 KB Output is correct
2 Correct 93 ms 27848 KB Output is correct
3 Correct 111 ms 27772 KB Output is correct
4 Correct 90 ms 27792 KB Output is correct
5 Correct 88 ms 27844 KB Output is correct
6 Correct 110 ms 27888 KB Output is correct
7 Correct 110 ms 28084 KB Output is correct
8 Correct 82 ms 27844 KB Output is correct
9 Correct 109 ms 40528 KB Output is correct
10 Correct 96 ms 35408 KB Output is correct
11 Correct 124 ms 32808 KB Output is correct
12 Correct 118 ms 32980 KB Output is correct
13 Correct 106 ms 33580 KB Output is correct
14 Correct 96 ms 33064 KB Output is correct
15 Correct 126 ms 32796 KB Output is correct
16 Correct 102 ms 33460 KB Output is correct
17 Correct 112 ms 27948 KB Output is correct
18 Correct 94 ms 28016 KB Output is correct
19 Correct 89 ms 27972 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 766 ms 60392 KB Output is correct
2 Correct 790 ms 60740 KB Output is correct
3 Correct 801 ms 60100 KB Output is correct
4 Correct 641 ms 60024 KB Output is correct
5 Correct 819 ms 59784 KB Output is correct
6 Correct 764 ms 59536 KB Output is correct
7 Correct 743 ms 59500 KB Output is correct
8 Correct 637 ms 60016 KB Output is correct
9 Correct 705 ms 54748 KB Output is correct
10 Correct 752 ms 54592 KB Output is correct
11 Correct 732 ms 54764 KB Output is correct
12 Correct 724 ms 54692 KB Output is correct
13 Correct 721 ms 54672 KB Output is correct
14 Correct 583 ms 54612 KB Output is correct
15 Correct 595 ms 54636 KB Output is correct
16 Correct 643 ms 55748 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 818 ms 56000 KB Output is correct
2 Correct 792 ms 55828 KB Output is correct
3 Correct 702 ms 55876 KB Output is correct
4 Correct 657 ms 55876 KB Output is correct
5 Correct 701 ms 54700 KB Output is correct
6 Correct 1241 ms 57912 KB Output is correct
7 Correct 1217 ms 58520 KB Output is correct
8 Correct 993 ms 58788 KB Output is correct
9 Correct 1079 ms 61296 KB Output is correct
10 Correct 953 ms 61072 KB Output is correct
11 Correct 1204 ms 60868 KB Output is correct
12 Correct 969 ms 60816 KB Output is correct
13 Correct 1192 ms 60928 KB Output is correct
14 Correct 1153 ms 60380 KB Output is correct
15 Correct 1049 ms 59620 KB Output is correct
16 Correct 1058 ms 59972 KB Output is correct
17 Correct 989 ms 59776 KB Output is correct
18 Correct 926 ms 60020 KB Output is correct
19 Correct 1086 ms 60128 KB Output is correct
20 Correct 730 ms 58948 KB Output is correct
21 Correct 834 ms 57648 KB Output is correct
22 Correct 869 ms 57568 KB Output is correct
23 Correct 826 ms 56504 KB Output is correct