Submission #603265

#	Time	Username	Problem	Language	Result	Execution time	Memory
603265		GusterGoose27	Railway Trip (JOI17_railway_trip)	C++11	0 / 100	135 ms	16812 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;
	int best = s;
	for (int i = 19; i >= 0; i--) {
		if (ranges[s][i].second < e) {
			best = ranges[s][i].second;
			pii r = ranges[s][i];
			if (heights[r.second] >= heights[r.first]) s = r.second;
			else s = r.first;
			ans += (1 << i);
		}
	}
	return pii(best, ans);
}

pii up_to_l(int s, int e) {
	int ans = 0;
	int best = s;
	for (int i = 19; i >= 0; i--) {
		if (ranges[s][i].first > e) {
			best = ranges[s][i].second;
			pii r = ranges[s][i];
			if (heights[r.first] >= heights[r.second]) s = r.first;
			else s = r.second;
			ans += (1 << i);
		}
	}
	return pii(best, 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++) {
			int h1 = heights[ranges[i][j-1].first];
			int h2 = heights[ranges[i][j-1].second];
			if (h1 >= h2) ranges[i][j].first = ranges[ranges[i][j-1].first][j-1].first;
			else ranges[i][j].first = ranges[ranges[i][j-1].second][j-1].first;
			if (h2 >= h1) ranges[i][j].second = ranges[ranges[i][j-1].second][j-1].second;
			else ranges[i][j].second = ranges[ranges[i][j-1].first][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: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55