oj.uz

Submission #1004296

# Submission time Handle Problem Language Result Execution time Memory
1004296 2024-06-21T07:23:02 Z Tob Railway Trip (JOI17_railway_trip) C++14
0 / 100
 78 ms 16700 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;
		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];
		if (nx2 == y) {
			cout << cnt << "\n";
			continue;
		}
		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);
		}
		int 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];
		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 <= 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

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 16652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 16700 KB Output isn't correct
2 Halted 0 ms 0 KB -