oj.uz

답안 #201338

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
201338 2020-02-10T08:31:00 Z maruii Railway Trip (JOI17_railway_trip) C++14
5 / 100
 214 ms 184040 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second
const int MX = 1e5 + 5;
const int MX2 = 1e6 + 5;

int N, K, Q, A[MX], stk[MX], stn, par[19][MX2], dst[19][MX2], dep[MX2], L[MX], R[MX], idx[MX2];
vector<int> edge[MX];
vector<pii> itv;
int lft(int x) { return 3 * x; }
int mid(int x) { return 3 * x + 1; }
int rht(int x) { return 3 * x + 2; }
void add_par(int x, int p, int a, int b, int i) {
	idx[x] = i;
	if (a < b) par[0][x] = lft(p);
	else if (a > b) par[0][x] = rht(p);
	else par[0][x] = mid(p);
	dst[0][x] = min(a, b);
	dep[x] = dep[par[0][x]] + 1;
	for (int i = 1; i < 19; ++i) {
		par[i][x] = par[i - 1][par[i - 1][x]];
		dst[i][x] = dst[i - 1][x] + dst[i - 1][par[i - 1][x]];
	}
}

int qry(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	int ret = 0;
	for (int i = 0; i < 19; ++i) if ((dep[x] - dep[y] >> i) & 1) {
		ret += dst[i][x];
		x = par[i][x];
	}
	for (int i = 18; i >= 0; --i) if (par[i][x] / 3 != par[i][y] / 3) {
		ret += dst[i][x] + dst[i][y];
		x = par[i][x], y = par[i][y];
	}
	if (idx[x] > idx[y]) swap(x, y);
	int a = x % 3, b = y % 3;
	int ret2 = ret + max(0, idx[y] - (b != 2) - idx[x] + (a == 0));
	if (par[0][x] < 3) return ret2;
	ret += dst[0][x] + dst[0][y];
	x = par[0][x], y = par[0][y];
	a = x % 3, b = y % 3;
	if (a == 1 || b == 1 || a + b != 2) return min(ret, ret2);
	return min(ret + 1, ret2);
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	itv.emplace_back(0, 1e9);
	cin >> N >> K >> Q;
	for (int i = 1; i <= N; ++i) cin >> A[i];
	for (int i = 1; i <= N; ++i) {
		while (stn && A[stk[stn - 1]] < A[i]) {
			stn--;
			itv.emplace_back(stk[stn], i - 1);
		}
		if (stn) itv.emplace_back(stk[stn - 1], i - 1);
		if (stn && A[i] == A[stk[stn - 1]]) stn--;
		stk[stn++] = i;
	}
	sort(itv.begin(), itv.end(), [&](pii a, pii b) {
		if (a.ff == b.ff) return a.ss > b.ss;
		return a.ff < b.ff;
	});
	stn = 0;
	for (int i = 0; i < itv.size(); ++i) {
		while (stn && itv[stk[stn - 1]].ss < itv[i].ff) --stn;
		if (stn) edge[stk[stn - 1]].push_back(i);
		stk[stn++] = i;
	}
	for (int i = 0; i < itv.size(); ++i) {
		int c = edge[i].size(), k = 0;
		for (auto j : edge[i]) {
			++k;
			int p = k - 1, q = c - k;
			add_par(lft(j), i, p, q + 1, k);
			add_par(mid(j), i, p, q, k);
			add_par(rht(j), i, p + 1, q, k);
			if (itv[j].ff == itv[j].ss) {
				L[itv[j].ff] = lft(j);
				R[itv[j].ff + 1] = rht(j);
			}
		}
	}
	while (Q--) {
		int x, y; cin >> x >> y;
		if (x > y) swap(x, y);
		printf("%d\n", qry(L[x], R[y]) - 1);
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 3064 KB Output is correct
2 Correct 8 ms 3192 KB Output is correct
3 Correct 6 ms 3064 KB Output is correct
4 Correct 6 ms 3064 KB Output is correct
5 Correct 6 ms 3064 KB Output is correct
6 Correct 6 ms 3064 KB Output is correct
7 Correct 6 ms 3064 KB Output is correct
8 Correct 6 ms 3064 KB Output is correct
9 Correct 6 ms 3064 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 3960 KB Output is correct
2 Runtime error 205 ms 177708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 214 ms 184040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 173 ms 115692 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -