oj.uz

Submission #603265

# Submission time Handle Problem Language Result Execution time Memory
603265 2022-07-23T19:53:35 Z GusterGoose27 Railway Trip (JOI17_railway_trip) C++11
0 / 100
 135 ms 16812 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 328 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Incorrect 37 ms 16452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 135 ms 16812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 16552 KB Output isn't correct
2 Halted 0 ms 0 KB -