oj.uz

Submission #603295

# Submission time Handle Problem Language Result Execution time Memory
603295 2022-07-23T21:57:26 Z GusterGoose27 Railway Trip (JOI17_railway_trip) C++11
100 / 100
 207 ms 18964 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;
	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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 48 ms 16448 KB Output is correct
3 Correct 47 ms 16604 KB Output is correct
4 Correct 43 ms 16632 KB Output is correct
5 Correct 50 ms 16588 KB Output is correct
6 Correct 46 ms 16736 KB Output is correct
7 Correct 48 ms 16928 KB Output is correct
8 Correct 38 ms 16472 KB Output is correct
9 Correct 44 ms 17148 KB Output is correct
10 Correct 43 ms 16840 KB Output is correct
11 Correct 42 ms 17004 KB Output is correct
12 Correct 43 ms 17012 KB Output is correct
13 Correct 42 ms 16844 KB Output is correct
14 Correct 45 ms 17020 KB Output is correct
15 Correct 51 ms 17000 KB Output is correct
16 Correct 44 ms 16964 KB Output is correct
17 Correct 45 ms 16940 KB Output is correct
18 Correct 41 ms 16944 KB Output is correct
19 Correct 42 ms 16944 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 17232 KB Output is correct
2 Correct 110 ms 18172 KB Output is correct
3 Correct 112 ms 18140 KB Output is correct
4 Correct 114 ms 18200 KB Output is correct
5 Correct 129 ms 18136 KB Output is correct
6 Correct 107 ms 18136 KB Output is correct
7 Correct 110 ms 18220 KB Output is correct
8 Correct 163 ms 18256 KB Output is correct
9 Correct 166 ms 18252 KB Output is correct
10 Correct 181 ms 18184 KB Output is correct
11 Correct 207 ms 18172 KB Output is correct
12 Correct 173 ms 18280 KB Output is correct
13 Correct 190 ms 18268 KB Output is correct
14 Correct 150 ms 18136 KB Output is correct
15 Correct 129 ms 18140 KB Output is correct
16 Correct 105 ms 17996 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 17120 KB Output is correct
2 Correct 91 ms 18252 KB Output is correct
3 Correct 90 ms 18252 KB Output is correct
4 Correct 95 ms 18328 KB Output is correct
5 Correct 185 ms 18380 KB Output is correct
6 Correct 153 ms 18796 KB Output is correct
7 Correct 137 ms 18796 KB Output is correct
8 Correct 172 ms 18496 KB Output is correct
9 Correct 127 ms 18648 KB Output is correct
10 Correct 129 ms 18708 KB Output is correct
11 Correct 155 ms 18508 KB Output is correct
12 Correct 136 ms 18672 KB Output is correct
13 Correct 121 ms 18636 KB Output is correct
14 Correct 145 ms 18872 KB Output is correct
15 Correct 141 ms 18800 KB Output is correct
16 Correct 138 ms 18964 KB Output is correct
17 Correct 127 ms 18708 KB Output is correct
18 Correct 127 ms 18676 KB Output is correct
19 Correct 125 ms 18612 KB Output is correct
20 Correct 104 ms 18400 KB Output is correct
21 Correct 93 ms 18300 KB Output is correct
22 Correct 88 ms 18380 KB Output is correct
23 Correct 88 ms 18284 KB Output is correct