oj.uz

Submission #415059

# Submission time Handle Problem Language Result Execution time Memory
415059 2021-05-31T13:28:39 Z amoo_safar Railway Trip (JOI17_railway_trip) C++17
45 / 100
 2000 ms 37316 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];
		}
		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 1 ms 1100 KB Output is correct
2 Correct 2 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 1100 KB Output is correct
6 Correct 2 ms 1100 KB Output is correct
7 Correct 2 ms 1100 KB Output is correct
8 Correct 2 ms 1100 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1228 KB Output is correct
2 Correct 17 ms 4400 KB Output is correct
3 Correct 17 ms 4284 KB Output is correct
4 Correct 19 ms 4300 KB Output is correct
5 Correct 17 ms 4320 KB Output is correct
6 Correct 17 ms 4372 KB Output is correct
7 Correct 19 ms 4404 KB Output is correct
8 Correct 13 ms 4660 KB Output is correct
9 Correct 41 ms 16916 KB Output is correct
10 Correct 37 ms 11924 KB Output is correct
11 Correct 27 ms 9220 KB Output is correct
12 Correct 33 ms 9324 KB Output is correct
13 Correct 27 ms 10008 KB Output is correct
14 Correct 30 ms 9420 KB Output is correct
15 Correct 26 ms 9208 KB Output is correct
16 Correct 31 ms 9752 KB Output is correct
17 Correct 21 ms 4356 KB Output is correct
18 Correct 20 ms 4292 KB Output is correct
19 Correct 18 ms 4376 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 36756 KB Output is correct
2 Correct 611 ms 37316 KB Output is correct
3 Correct 578 ms 36540 KB Output is correct
4 Correct 623 ms 36480 KB Output is correct
5 Correct 650 ms 36256 KB Output is correct
6 Correct 650 ms 36072 KB Output is correct
7 Correct 548 ms 36020 KB Output is correct
8 Correct 523 ms 36468 KB Output is correct
9 Correct 638 ms 31152 KB Output is correct
10 Correct 625 ms 31088 KB Output is correct
11 Correct 585 ms 31336 KB Output is correct
12 Correct 559 ms 31100 KB Output is correct
13 Correct 580 ms 31212 KB Output is correct
14 Correct 511 ms 31148 KB Output is correct
15 Correct 563 ms 31240 KB Output is correct
16 Correct 536 ms 32224 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 633 ms 32296 KB Output is correct
2 Correct 617 ms 32380 KB Output is correct
3 Correct 633 ms 32468 KB Output is correct
4 Correct 670 ms 32324 KB Output is correct
5 Correct 620 ms 31228 KB Output is correct
6 Execution timed out 2084 ms 34764 KB Time limit exceeded
7 Halted 0 ms 0 KB -