제출 #1229631

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1229631		PenguinsAreCute	Railway Trip (JOI17_railway_trip)	C++17	0 / 100	1823 ms	5220 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], rgt[n];
	stack<int> s;
	for(int i=0;i<n;i++) {
		while(s.size() && lvl[s.top()] < lvl[i])
			s.pop();
		lft[i] = (s.size()&&lvl[s.top()]>lvl[i]?s.top():-1);
		s.push(i);
	}
	while(s.size())
		s.pop();
	for(int i=n;i--;) {
		while(s.size() && lvl[s.top()] < lvl[i])
			s.pop();
		rgt[i] = (s.size()?s.top():-1);
		s.push(i);
	}
	auto cmp = [&lvl](int x, int y) -> bool {
		if(y == -1)
			return 0;
		if(x == -1)
			return 1;
		return (lvl[x] < lvl[y]) || (lvl[x] == lvl[y] && x < y);
	};
	for(int i=0;i<n;i++) {
		if(lft[i] == -1)
			lft[i] = rgt[i];
		if(rgt[i] == -1)
			rgt[i] = lft[i];
		if(lft[i] != -1 && cmp(rgt[i], lft[i]))
			swap(lft[i], rgt[i]);
	}
	int height[n];
	memset(height,0,sizeof(height));
	int ord[n];
	iota(ord,ord+n,0);
	sort(ord,ord+n,cmp);
	for(int i=n-1;i--;)
		height[ord[i]] = height[lft[ord[i]]] + 1;
	while(q--) {
		int a, b, l;
		cin >> a >> b;
		a--; b--;
		int ans = 0;
		l = a;
		for(int c=a,d=b;c!=d;) {
			if(height[c] > height[d])
				swap(c, d);
			l = d = lft[d];
		}
		while(rgt[a] != -1 && height[l] <= height[rgt[a]])
			a = rgt[a], ans++;
		while(rgt[b] != -1 && height[l] <= height[rgt[b]])
			b = rgt[b], ans++;
		int dir = height[a] + height[b] - 2 * height[l];
		int liftA = ~rgt[a] ? abs(height[rgt[a]] - height[b]) + 1 : 1e7;
		int liftB = ~rgt[b] ? abs(height[rgt[b]] - height[a]) + 1 : 1e7;
		int liftBoth = ~rgt[a] && ~rgt[b] ? abs(height[rgt[a]] - height[rgt[b]]) + 2 : 1e7;
		cout << ans + min({dir,liftA,liftB,liftBoth})-1 << "\n";
	}
}

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