oj.uz

Submission #1004452

# Submission time Handle Problem Language Result Execution time Memory
1004452 2024-06-21T09:09:34 Z Tob Railway Trip (JOI17_railway_trip) C++14
100 / 100
 96 ms 17256 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);
		}
		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;
			cnt += (1 << i);
		}
		cout << cnt << "\n";
	}

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 416 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 468 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 16 ms 14940 KB Output is correct
3 Correct 19 ms 14940 KB Output is correct
4 Correct 17 ms 15196 KB Output is correct
5 Correct 15 ms 15196 KB Output is correct
6 Correct 16 ms 15176 KB Output is correct
7 Correct 18 ms 15336 KB Output is correct
8 Correct 19 ms 14936 KB Output is correct
9 Correct 25 ms 15448 KB Output is correct
10 Correct 18 ms 15292 KB Output is correct
11 Correct 19 ms 15452 KB Output is correct
12 Correct 18 ms 15452 KB Output is correct
13 Correct 18 ms 15360 KB Output is correct
14 Correct 18 ms 15560 KB Output is correct
15 Correct 21 ms 15400 KB Output is correct
16 Correct 23 ms 15452 KB Output is correct
17 Correct 19 ms 15452 KB Output is correct
18 Correct 16 ms 15528 KB Output is correct
19 Correct 17 ms 15448 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 16720 KB Output is correct
2 Correct 59 ms 16724 KB Output is correct
3 Correct 59 ms 16724 KB Output is correct
4 Correct 74 ms 16684 KB Output is correct
5 Correct 62 ms 16708 KB Output is correct
6 Correct 58 ms 16696 KB Output is correct
7 Correct 58 ms 16724 KB Output is correct
8 Correct 68 ms 16584 KB Output is correct
9 Correct 75 ms 16720 KB Output is correct
10 Correct 96 ms 16724 KB Output is correct
11 Correct 74 ms 16804 KB Output is correct
12 Correct 75 ms 16716 KB Output is correct
13 Correct 89 ms 16836 KB Output is correct
14 Correct 72 ms 17032 KB Output is correct
15 Correct 59 ms 16500 KB Output is correct
16 Correct 56 ms 16464 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 16724 KB Output is correct
2 Correct 57 ms 16700 KB Output is correct
3 Correct 39 ms 16720 KB Output is correct
4 Correct 40 ms 16728 KB Output is correct
5 Correct 64 ms 16616 KB Output is correct
6 Correct 62 ms 17256 KB Output is correct
7 Correct 65 ms 17204 KB Output is correct
8 Correct 65 ms 17036 KB Output is correct
9 Correct 60 ms 16976 KB Output is correct
10 Correct 70 ms 17092 KB Output is correct
11 Correct 59 ms 17132 KB Output is correct
12 Correct 64 ms 16992 KB Output is correct
13 Correct 59 ms 17172 KB Output is correct
14 Correct 64 ms 17100 KB Output is correct
15 Correct 60 ms 17232 KB Output is correct
16 Correct 66 ms 17236 KB Output is correct
17 Correct 69 ms 17232 KB Output is correct
18 Correct 68 ms 17236 KB Output is correct
19 Correct 65 ms 17232 KB Output is correct
20 Correct 57 ms 17040 KB Output is correct
21 Correct 46 ms 16720 KB Output is correct
22 Correct 54 ms 16724 KB Output is correct
23 Correct 49 ms 16880 KB Output is correct