oj.uz

Submission #805976

# Submission time Handle Problem Language Result Execution time Memory
805976 2023-08-04T04:04:46 Z MetalPower Railway Trip (JOI17_railway_trip) C++14
100 / 100
 149 ms 18048 KB 
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define fi first
#define se second

const int MX = 1e5 + 10;
const int LG = 18;
const int INF = 1e9 + 7;

int N, K, Q, arr[MX], lf[MX], rg[MX], L[MX][LG], R[MX][LG];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> K >> Q;
	for(int i = 1; i <= N; i++) cin >> arr[i];

	{
		vector<int> stk;
		for(int i = 1; i <= N; i++){
			for(; !stk.empty() && arr[stk.back()] < arr[i]; ) stk.pop_back();
			if(!stk.empty()) lf[i] = stk.back();
			else lf[i] = 0;
			stk.push_back(i);
		}
		stk.clear();
	}

	{
		vector<int> stk;
		for(int i = N; i >= 1; i--){
			for(; !stk.empty() && arr[stk.back()] < arr[i]; ) stk.pop_back();
			if(!stk.empty()) rg[i] = stk.back();
			else rg[i] = MX - 1;
			stk.push_back(i);
		}
	}

	for(int j = 0; j < LG; j++){

		R[0][j] = L[0][j] = 0; L[MX - 1][j] = R[MX - 1][j] = MX - 1;

		if(j == 0){
			for(int i = 1; i <= N; i++) L[i][j] = lf[i], R[i][j] = rg[i];
		}else{
			for(int i = 1; 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[L[i][j - 1]][j - 1], R[R[i][j - 1]][j - 1]);
			}
		}
	}

	for(int q = 0; q < Q; q++){
		int a, b; cin >> a >> b;
		if(a > b) swap(a, b);

		int la = a, ra = a, ans = 0;
		for(int j = LG - 1; j >= 0; j--){
			if(max(R[ra][j], R[la][j]) <= b){
				ans += 1 << j;
				int temp_la = la, temp_ra = ra;
				la = min(L[temp_la][j], L[temp_ra][j]), ra = max(R[temp_la][j], R[temp_ra][j]);
			}
		}

		int lb = b, rb = b;
		for(int j = LG - 1; j >= 0; j--){
			if(min(L[lb][j], L[rb][j]) >= ra){
				ans += 1 << j;
				int tl = lb, tr = rb;
				lb = min(L[tl][j], L[tr][j]), rb = max(R[tl][j], R[tr][j]);
			}
		}

		if(ra == lb) ans--;
		cout << ans << '\n';
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 324 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 0 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 23 ms 15848 KB Output is correct
3 Correct 22 ms 15828 KB Output is correct
4 Correct 21 ms 15828 KB Output is correct
5 Correct 21 ms 15760 KB Output is correct
6 Correct 22 ms 15936 KB Output is correct
7 Correct 23 ms 16132 KB Output is correct
8 Correct 21 ms 15816 KB Output is correct
9 Correct 26 ms 16300 KB Output is correct
10 Correct 21 ms 16112 KB Output is correct
11 Correct 24 ms 16208 KB Output is correct
12 Correct 25 ms 16272 KB Output is correct
13 Correct 25 ms 16176 KB Output is correct
14 Correct 24 ms 16284 KB Output is correct
15 Correct 24 ms 16228 KB Output is correct
16 Correct 24 ms 16176 KB Output is correct
17 Correct 23 ms 16172 KB Output is correct
18 Correct 25 ms 16084 KB Output is correct
19 Correct 22 ms 16168 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 17484 KB Output is correct
2 Correct 76 ms 17448 KB Output is correct
3 Correct 78 ms 17488 KB Output is correct
4 Correct 75 ms 17400 KB Output is correct
5 Correct 95 ms 17448 KB Output is correct
6 Correct 75 ms 17452 KB Output is correct
7 Correct 76 ms 17380 KB Output is correct
8 Correct 93 ms 17596 KB Output is correct
9 Correct 149 ms 17604 KB Output is correct
10 Correct 113 ms 17616 KB Output is correct
11 Correct 114 ms 17620 KB Output is correct
12 Correct 144 ms 17624 KB Output is correct
13 Correct 104 ms 17592 KB Output is correct
14 Correct 108 ms 17480 KB Output is correct
15 Correct 85 ms 17404 KB Output is correct
16 Correct 80 ms 17296 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 17488 KB Output is correct
2 Correct 72 ms 17636 KB Output is correct
3 Correct 59 ms 17368 KB Output is correct
4 Correct 58 ms 17484 KB Output is correct
5 Correct 120 ms 17616 KB Output is correct
6 Correct 98 ms 17892 KB Output is correct
7 Correct 118 ms 17976 KB Output is correct
8 Correct 90 ms 17780 KB Output is correct
9 Correct 94 ms 17916 KB Output is correct
10 Correct 109 ms 17832 KB Output is correct
11 Correct 97 ms 18048 KB Output is correct
12 Correct 82 ms 17844 KB Output is correct
13 Correct 79 ms 17824 KB Output is correct
14 Correct 85 ms 17908 KB Output is correct
15 Correct 121 ms 17928 KB Output is correct
16 Correct 105 ms 17896 KB Output is correct
17 Correct 96 ms 17912 KB Output is correct
18 Correct 84 ms 17936 KB Output is correct
19 Correct 84 ms 17860 KB Output is correct
20 Correct 89 ms 17628 KB Output is correct
21 Correct 61 ms 17536 KB Output is correct
22 Correct 60 ms 17548 KB Output is correct
23 Correct 60 ms 17496 KB Output is correct