Submission #1229771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229771		PenguinsAreCute	Railway Trip (JOI17_railway_trip)	C++17	0 / 100	146 ms	5412 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()?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);
	}
	vector<int> swp(n, 0);
	for(int i=0;i<n;i++) {
		if(rgt[i] != -1) {
			swp[i+1] ^= 1;
			swp[rgt[i]] ^= 1;
		}
		if(lft[i] != -1 && lvl[lft[i]] != lvl[i]) {
			swp[lft[i]+1] ^= 1;
			swp[i] ^= 1;
		}
	}
	partial_sum(swp.begin(),swp.end(),swp.begin());
	auto cmp = [&lvl,&swp](int x, int y) -> bool {
		if(lvl[x] != lvl[y])
			return lvl[x] < lvl[y];
		if(swp[x] & 1)
			return x > y;
		return x < y;
	};
	for(int i=0;i<n;i++) {
		if(lft[i] == -1 || cmp(lft[i], i))
			lft[i] = rgt[i];
		if(rgt[i] == -1 || cmp(rgt[i], i))
			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