oj.uz

답안 #415052

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
415052 2021-05-31T13:25:27 Z amoo_safar Railway Trip (JOI17_railway_trip) C++17
20 / 100
 2000 ms 36004 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][Log], po = 0;
int WW[N][Log];

map<T, int> mp;
// map<int, T> rv;
T rv[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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 1 ms 1100 KB Output is correct
9 Correct 2 ms 1100 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1228 KB Output is correct
2 Correct 21 ms 4620 KB Output is correct
3 Correct 17 ms 4568 KB Output is correct
4 Correct 18 ms 4636 KB Output is correct
5 Correct 18 ms 4556 KB Output is correct
6 Correct 18 ms 4640 KB Output is correct
7 Correct 19 ms 4812 KB Output is correct
8 Correct 13 ms 4940 KB Output is correct
9 Correct 49 ms 17424 KB Output is correct
10 Correct 33 ms 12244 KB Output is correct
11 Correct 29 ms 9664 KB Output is correct
12 Correct 31 ms 9700 KB Output is correct
13 Correct 31 ms 10360 KB Output is correct
14 Correct 32 ms 9800 KB Output is correct
15 Correct 33 ms 9564 KB Output is correct
16 Correct 32 ms 10204 KB Output is correct
17 Correct 20 ms 4784 KB Output is correct
18 Correct 19 ms 4728 KB Output is correct
19 Correct 17 ms 4728 KB Output is correct

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 575 ms 36004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 702 ms 33484 KB Output is correct
2 Correct 694 ms 34388 KB Output is correct
3 Correct 620 ms 33948 KB Output is correct
4 Correct 616 ms 34104 KB Output is correct
5 Correct 580 ms 32564 KB Output is correct
6 Execution timed out 2065 ms 23392 KB Time limit exceeded
7 Halted 0 ms 0 KB -