oj.uz

Submission #415054

# Submission time Handle Problem Language Result Execution time Memory
415054 2021-05-31T13:26:57 Z amoo_safar Railway Trip (JOI17_railway_trip) C++17
45 / 100
 2000 ms 37300 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 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];
		}
		// debug(res);
		// while(a[s1.F] < mx){
		// 	auto del = nxt(s1);
		// 	if(a[del.S.F] >= mx) break;
		// 	cnt ++;
		// 	res += del.F;
		// 	s1 = del.S;
		// }
		// debug(res);
		// assert(s1 == rv[id]);
		s1 = rv[id];
		// cerr << "!! " << s1.F << ' ' << s1.S << ' ' << rv[id].F << ' ' << rv[id].S << '\n';
		pii s2 = {des, des};
		id = Calc(s2);
		while(a[s2.F] < mx){
			auto del = nxt(s2);
			if(a[del.S.F] >= mx) break;
			cnt ++;
			res += del.F;
			s2 = del.S;
		}
		assert(cnt < k + k + 10);
		// 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 1100 KB Output is correct
4 Correct 2 ms 1100 KB Output is correct
5 Correct 2 ms 1172 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 1228 KB Output is correct
2 Correct 16 ms 4300 KB Output is correct
3 Correct 19 ms 4336 KB Output is correct
4 Correct 19 ms 4268 KB Output is correct
5 Correct 17 ms 4300 KB Output is correct
6 Correct 18 ms 4292 KB Output is correct
7 Correct 20 ms 4300 KB Output is correct
8 Correct 13 ms 4760 KB Output is correct
9 Correct 46 ms 16968 KB Output is correct
10 Correct 36 ms 11908 KB Output is correct
11 Correct 32 ms 9176 KB Output is correct
12 Correct 35 ms 9340 KB Output is correct
13 Correct 31 ms 10008 KB Output is correct
14 Correct 35 ms 9404 KB Output is correct
15 Correct 29 ms 9236 KB Output is correct
16 Correct 33 ms 9704 KB Output is correct
17 Correct 20 ms 4332 KB Output is correct
18 Correct 20 ms 4300 KB Output is correct
19 Correct 16 ms 4280 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 664 ms 36776 KB Output is correct
2 Correct 531 ms 37300 KB Output is correct
3 Correct 667 ms 36580 KB Output is correct
4 Correct 662 ms 36328 KB Output is correct
5 Correct 616 ms 36224 KB Output is correct
6 Correct 691 ms 36068 KB Output is correct
7 Correct 504 ms 36016 KB Output is correct
8 Correct 492 ms 36472 KB Output is correct
9 Correct 508 ms 31220 KB Output is correct
10 Correct 533 ms 31100 KB Output is correct
11 Correct 573 ms 31344 KB Output is correct
12 Correct 496 ms 31132 KB Output is correct
13 Correct 564 ms 31124 KB Output is correct
14 Correct 546 ms 31088 KB Output is correct
15 Correct 509 ms 31132 KB Output is correct
16 Correct 517 ms 32400 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 32268 KB Output is correct
2 Correct 655 ms 32356 KB Output is correct
3 Correct 583 ms 32364 KB Output is correct
4 Correct 609 ms 32296 KB Output is correct
5 Correct 563 ms 31156 KB Output is correct
6 Execution timed out 2095 ms 22580 KB Time limit exceeded
7 Halted 0 ms 0 KB -