oj.uz

답안 #1004436

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1004436 2024-06-21T08:56:42 Z Tob Railway Trip (JOI17_railway_trip) C++14
0 / 100
 78 ms 16760 KB 
#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 1e5 + 7, lg = 17;

int n, k, q;
int a[N], l[N][lg+1], r[N][lg+1];

int main () {
	FIO;
	cin >> n >> k >> q;
	
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	stack <int> st;
	st.push(0);
	for (int i = 1; i < n; i++) {
		while (!st.empty() && a[st.top()] <= a[i]) {r[st.top()][0] = i; st.pop();}
		st.push(i);
	}
	r[n-1][0] = n-1;
	st.pop();
	st.push(n-1);
	for (int i = n-2; i >= 0; i--) {
		while (!st.empty() && a[st.top()] <= a[i]) {l[st.top()][0] = i; st.pop();}
		st.push(i);
	}
	
	for (int j = 1; j <= lg; j++) {
		for (int i = 0; i < n; i++) {
			l[i][j] = min(l[l[i][j-1]][j-1], l[r[i][j-1]][j-1]);
			r[i][j] = max(r[r[i][j-1]][j-1], r[l[i][j-1]][j-1]);
		}
	}
	
	while (q--) {
		int x, y; cin >> x >> y; x--; y--; if (x > y) swap(x, y);
		int cnt = 0, lo = x, hi = x, re = 1e9;
		for (int i = lg; i >= 0; i--) {
			int nlo = min(l[lo][i], l[hi][i]), nhi = max(r[lo][i], r[hi][i]);
			if (nhi >= y) continue;
			lo = nlo; hi = nhi;
			cnt += (1 << i);
		}
		int nx1 = hi, nx2 = r[hi][0], nx3 = r[lo][0];
		if (nx2 == y) re = cnt;
		int cnt2 = 0; lo = hi = y;
		for (int i = lg; i >= 0; i--) {
			int nlo = min(l[lo][i], l[hi][i]), nhi = max(r[lo][i], r[hi][i]);
			if (nlo <= nx1) continue;
			lo = nlo; hi = nhi;
			cnt2 += (1 << i);
		}
		if (l[lo][0] != nx1 && l[hi][0] != nx1) nx2 = nx3;
		else re = min(re, cnt+cnt2);
		cnt2 = 0; lo = hi = y;
		for (int i = lg; i >= 0; i--) {
			int nlo = min(l[lo][i], l[hi][i]), nhi = max(r[lo][i], r[hi][i]);
			if (nhi >= nx2) continue;
			lo = nlo; hi = nhi;
			cnt2 += (1 << i);
		}
		re = min(re, cnt+cnt2+1);
		cnt = 0; lo = hi = y;
		for (int i = lg; i >= 0; i--) {
			int nlo = min(l[lo][i], l[hi][i]), nhi = max(r[lo][i], r[hi][i]);
			if (nlo <= x) continue;
			lo = nlo; hi = nhi;
			cnt += (1 << i);
		}
		int ny = ((l[lo][0] <= x) ? l[lo][0] : l[hi][0]);
		cnt2 = 0; lo = hi = x;
		for (int i = lg; i >= 0; i--) {
			int nlo = min(l[lo][i], l[hi][i]), nhi = max(r[lo][i], r[hi][i]);
			if (nlo <= ny) continue;
			lo = nlo; hi = nhi;
			cnt2 += (1 << i);
		}
		re = min(re, cnt+cnt2+1);
		cout << re << "\n";
	}

	return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 472 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 55.0

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