Submission #1229796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229796		PenguinsAreCute	Railway Trip (JOI17_railway_trip)	C++17	45 / 100	2096 ms	5524 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, k, q;
	cin >> n >> k >> q;
	vector<int> lvl(n);
	vector<int> adj[n];
	for(int i=0;i<n;i++)
		cin >> lvl[i];
	int lft[n], distl[n], rgt[n], distr[n];
	stack<int> s;
	for(int i=0;i<n;i++) {
		while(s.size() && lvl[s.top()] < lvl[i])
			s.pop();
		if(s.size()) {
			if(lvl[s.top()] == lvl[i])
				lft[i] = lft[s.top()], distl[i] = distl[s.top()] + 1;
			else
				lft[i] = s.top(), distl[i] = 1;
		} else
			lft[i] = -1, distl[i] = 0;
		s.push(i);
	}
	while(s.size())
		s.pop();
	for(int i=n;i--;) {
		while(s.size() && lvl[s.top()] < lvl[i])
			s.pop();
		if(s.size()) {
			if(lvl[s.top()] == lvl[i])
				rgt[i] = rgt[s.top()], distr[i] = distr[s.top()] + 1;
			else
				rgt[i] = s.top(), distr[i] = 1;
		} else
			rgt[i] = -1, distr[i] = 0;
		s.push(i);
	}
	/*
	for(int i=0;i<n;i++)
		printf("lft rgt dl dr %d = %d %d %d %d\n",i,lft[i],rgt[i],distl[i],distr[i]);
	*/
	while(q--) {
		int alv, arv, blv, brv, ald = 0, ard = 0, bld = 0, brd = 0, ans = 1e9;
		cin >> alv >> blv;
		arv = --alv;
		brv = --blv;
		for(int i=2;1;i++) {
			if(lft[alv] == lft[blv] && lvl[alv] == lvl[blv])
				ans = min(ans, abs(distl[blv] - distl[alv]) + ald + bld);
			if(lft[alv] == lft[brv] && lvl[alv] == lvl[brv])
				ans = min(ans, abs(distl[brv] - distl[alv]) + ald + brd);
			if(lft[arv] == lft[blv] && lvl[arv] == lvl[blv])
				ans = min(ans, abs(distl[blv] - distl[arv]) + ard + bld);
			if(lft[arv] == lft[brv] && lvl[arv] == lvl[brv])
				ans = min(ans, abs(distl[brv] - distl[arv]) + ard + brd);
			if(i == k + 1)
				break;
			if(lvl[alv] < i) {
				ald += distl[alv];
				alv = lft[alv];
			}
			if(lvl[arv] < i) {
				ard += distr[arv];
				arv = rgt[arv];
			}
			if(lvl[blv] < i) {
				bld += distl[blv];
				blv = lft[blv];
			}
			if(lvl[brv] < i) {
				brd += distr[brv];
				brv = rgt[brv];
			}
			ald = min(ald, ard + 1);
			ard = min(ard, ald + 1);
			bld = min(bld, brd + 1);
			brd = min(brd, bld + 1);
		}
		cout << ans - 1 << "\n";
	}
}

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