Submission #116622

#	Time	Username	Problem	Language	Result	Execution time	Memory
116622		tmwilliamlin168	Railway Trip (JOI17_railway_trip)	C++14	100 / 100	267 ms	14968 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;

const int mxN=1e5;
int n, k, q, l[mxN], nl[17][mxN], nr[17][mxN];

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

	cin >> n >> k >> q;
	for(int i=0; i<n; ++i) {
		cin >> l[i];
		nl[0][i]=i-1;
		while(~nl[0][i]&&l[nl[0][i]]<l[i])
			nl[0][i]=nl[0][nl[0][i]];
	}
	nl[0][0]=0;
	for(int i=n-1; ~i; --i) {
		nr[0][i]=i+1;
		while(nr[0][i]<n&&l[nr[0][i]]<l[i])
			nr[0][i]=nr[0][nr[0][i]];
	}
	nr[0][n-1]=n-1;
	for(int i=1; i<17; ++i) {
		for(int j=0; j<n; ++j) {
			nl[i][j]=min(nl[i-1][nl[i-1][j]], nl[i-1][nr[i-1][j]]);
			nr[i][j]=max(nr[i-1][nl[i-1][j]], nr[i-1][nr[i-1][j]]);
		}
	}
	for(int a, b; q--; ) {
		cin >> a >> b, --a, --b;
		if(a>b)
			swap(a, b);
		int l=a, r=a, ans=0, c;
		for(int i=16; ~i; --i) {
			if(max(nr[i][l], nr[i][r])<b) {
				tie(l, r)=make_pair(min(nl[i][l], nl[i][r]), max(nr[i][l], nr[i][r]));
				ans+=1<<i;
			}
		}
		c=r;
		l=b, r=b;
		for(int i=16; ~i; --i) {
			if(min(nl[i][l], nl[i][r])>c) {
				tie(l, r)=make_pair(min(nl[i][l], nl[i][r]), max(nr[i][l], nr[i][r]));
				ans+=1<<i;
			}
		}
		cout << ans << "\n";
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55