Submission #745421

#	Time	Username	Problem	Language	Result	Execution time	Memory
745421		blue	Railway Trip (JOI17_railway_trip)	C++17	100 / 100	259 ms	17092 KiB

railway_trip

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

using vi = vector<int>;
using vvi = vector<vi>;

const int lg = 17;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, K, Q;
	cin >> N >> K >> Q;

	vi L(1+N);
	for(int i = 1; i <= N; i++)
		cin >> L[i];


	int lh[1+lg][1+N], rh[1+lg][1+N];

	lh[0][1] = 1;
	for(int i = 2; i <= N; i++)
	{
		lh[0][i] = i-1;
		while(L[lh[0][i]] < L[i])
			lh[0][i] = lh[0][ lh[0][i] ];
	}

	rh[0][N] = N;
	for(int i = N-1; i >= 1; i--)
	{
		rh[0][i] = i+1;
		while(L[rh[0][i]] < L[i])
			rh[0][i] = rh[0][ rh[0][i] ];
	}

	for(int e = 1; e <= lg; e++)
	{
		for(int i = 1; i <= N; i++)
		{
			lh[e][i] = min(lh[e-1][lh[e-1][i]], lh[e-1][rh[e-1][i]]);
			rh[e][i] = max(rh[e-1][rh[e-1][i]], rh[e-1][lh[e-1][i]]);
		}
	}

	// cerr << "done\n";

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

		if(a > b)
			swap(a, b);

		int res = 0;

		int la = a, ra = a;
		for(int e = lg; e >= 0; e--)
		{
			if(max(rh[e][la], rh[e][ra]) < b)
			{
				res += (1<<e);

				int nla = min(lh[e][la], lh[e][ra]);
				int nra = max(rh[e][la], rh[e][ra]);

				la = nla;
				ra = nra;
			}
		}


		int lb = b, rb = b;
		for(int e = lg; e >= 0; e--)
		{
			if(min(lh[e][lb], lh[e][rb]) > ra)
			{
				res += (1<<e);

				int nlb = min(lh[e][lb], lh[e][rb]);
				int nrb = max(rh[e][lb], rh[e][rb]);

				lb = nlb;
				rb = nrb;
			}
		}

		cout << res << '\n';
	}
}

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