oj.uz

Submission #1004265

# Submission time Handle Problem Language Result Execution time Memory
1004265 2024-06-21T07:00:01 Z Tob Railway Trip (JOI17_railway_trip) C++14
0 / 100
 57 ms 16772 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 nx = r[hi][0];
		if (nx == y) {
			cout << cnt << "\n";
			continue;
		}
		int cnt2 = 0; x = hi; 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;
			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 >= nx) continue;
			lo = nlo; hi = nhi;
			cnt2 += (1 << i);
		}
		cout << min(re, cnt+cnt2+1) << "\n";
	}

	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2396 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 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

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

Subtask #4
0 / 55.0

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