oj.uz

답안 #415053

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
415053 2021-05-31T13:26:25 Z amoo_safar Railway Trip (JOI17_railway_trip) C++17
20 / 100
 2000 ms 70736 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];

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 2 ms 1100 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1136 KB Output is correct
2 Correct 16 ms 4352 KB Output is correct
3 Correct 17 ms 4340 KB Output is correct
4 Correct 17 ms 4300 KB Output is correct
5 Correct 17 ms 4300 KB Output is correct
6 Correct 17 ms 4316 KB Output is correct
7 Correct 19 ms 4300 KB Output is correct
8 Correct 13 ms 4764 KB Output is correct
9 Correct 44 ms 16904 KB Output is correct
10 Correct 33 ms 11880 KB Output is correct
11 Correct 29 ms 9200 KB Output is correct
12 Correct 30 ms 9376 KB Output is correct
13 Correct 28 ms 9968 KB Output is correct
14 Correct 30 ms 9380 KB Output is correct
15 Correct 30 ms 9180 KB Output is correct
16 Correct 31 ms 9724 KB Output is correct
17 Correct 18 ms 4360 KB Output is correct
18 Correct 20 ms 4300 KB Output is correct
19 Correct 16 ms 4300 KB Output is correct

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 447 ms 70736 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 616 ms 32260 KB Output is correct
2 Correct 660 ms 32272 KB Output is correct
3 Correct 545 ms 32308 KB Output is correct
4 Correct 598 ms 32324 KB Output is correct
5 Correct 481 ms 31152 KB Output is correct
6 Execution timed out 2080 ms 22652 KB Time limit exceeded
7 Halted 0 ms 0 KB -