Submission #805976

#	Time	Username	Problem	Language	Result	Execution time	Memory
805976		MetalPower	Railway Trip (JOI17_railway_trip)	C++14	100 / 100	149 ms	18048 KiB

railway_trip

#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 / 5
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55