Submission #603295

#	Time	Username	Problem	Language	Result	Execution time	Memory
603295		GusterGoose27	Railway Trip (JOI17_railway_trip)	C++11	100 / 100	207 ms	18964 KiB

railway_trip

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e5;
int n, k, m;
pii ranges[MAXN][20];
int heights[MAXN];

pii up_to_r(int s, int e) {
	int ans = 0;
	pii cur(s, s);
	for (int i = 19; i >= 0; i--) {
		if (max(ranges[cur.first][i].second, ranges[cur.second][i].second) < e) {
			int nextl = min(ranges[cur.first][i].first, ranges[cur.second][i].first);
			int nextr = max(ranges[cur.first][i].second, ranges[cur.second][i].second);
			cur = pii(nextl, nextr);
			ans += (1 << i);
		}
	}
	return pii(cur.second, ans);
}

pii up_to_l(int s, int e) {
	int ans = 0;
	pii cur(s, s);
	for (int i = 19; i >= 0; i--) {
		if (min(ranges[cur.first][i].first, ranges[cur.second][i].first) > e) {
			int nextl = min(ranges[cur.first][i].first, ranges[cur.second][i].first);
			int nextr = max(ranges[cur.first][i].second, ranges[cur.second][i].second);
			cur = pii(nextl, nextr);
			ans += (1 << i);
		}
	}
	return pii(cur.first, ans);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> k >> m;
	for (int i = 0; i < n; i++) cin >> heights[i];
	vector<int> q;
	q.push_back(0);
	ranges[0][0].first = 0;
	ranges[n-1][0].second = n-1;
	for (int i = 1; i < n; i++) {
		while (q.size() && heights[i] >= heights[q.back()]) {
			int v = q.back();
			ranges[v][0].second = i;
			q.pop_back();
		}
		q.push_back(i);
	}
	q.clear();
	q.push_back(n-1);
	for (int i = n-2; i >= 0; i--) {
		while (q.size() && heights[i] >= heights[q.back()]) {
			int v = q.back();
			ranges[v][0].first = i;
			q.pop_back();
		}
		q.push_back(i);
	}
	for (int j = 1; j < 20; j++) {
		for (int i = 0; i < n; i++) {
			ranges[i][j].first = min(ranges[ranges[i][j-1].first][j-1].first, ranges[ranges[i][j-1].second][j-1].first);
			ranges[i][j].second = max(ranges[ranges[i][j-1].first][j-1].second, ranges[ranges[i][j-1].second][j-1].second);
		}
	}
	for (int i = 0; i < m; i++) {
		int x, y; cin >> x >> y;
		x--; y--;
		if (x > y) swap(x, y);
		pii far_right = up_to_r(x, y);
		pii far_left = up_to_l(y, far_right.first);
		cout << (far_right.second+far_left.second) << "\n";
	}
}

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