oj.uz

Submission #984828

# Submission time Handle Problem Language Result Execution time Memory
984828 2024-05-17T06:27:59 Z pavement Escape Route 2 (JOI24_escape2) C++17
23 / 100
 246 ms 26372 KB 
#include <bits/stdc++.h>
using namespace std;

using ii = pair<int, int>;
using ll = long long;

#define mp make_pair
#define pb push_back
#define eb emplace_back

int N, T, Q, _idx, M[100005], anc[25][100005];
ll dep[100005];
vector<int> idx[100005];
vector<ii> V[100005];

ll f(int u, int k) {
	int v = u;
	for (int j = 0; j < 20; j++) {
		if (k & (1 << j)) {
			v = anc[j][v];
		}
	}
	return dep[u] - dep[v];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> T;
	for (int i = 1; i < N; i++) {
		cin >> M[i];
		for (int j = 0, a, b; j < M[i]; j++) {
			cin >> a >> b;
			V[i].eb(a, b);
			idx[i].pb(++_idx);
		}
		sort(V[i].begin(), V[i].end());
		for (int j = (int)V[i].size() - 1, sf = (int)2e9; j >= 0; j--) {
			sf = min(sf, V[i][j].second);
			V[i][j].second = sf;
		}
	}
	for (int i = N - 2; i >= 1; i--) {
		for (int j = 0; j < M[i]; j++) {
			int tmp = lower_bound(V[i + 1].begin(), V[i + 1].end(), mp(V[i][j].second, -1)) - V[i + 1].begin();
			ii potential_to = mp(V[i + 1][0].second + T - V[i][j].second, idx[i + 1][0]);
			if (tmp < (int)V[i + 1].size()) {
				potential_to = min(potential_to, mp(V[i + 1][tmp].second - V[i][j].second, idx[i + 1][tmp]));
			}
			anc[0][idx[i][j]] = potential_to.second;
			for (int k = 1; k <= 20; k++) {
				if (anc[k - 1][idx[i][j]] == 0) {
					break;
				}
				anc[k][idx[i][j]] = anc[k - 1][anc[k - 1][idx[i][j]]];
			}
			dep[idx[i][j]] = dep[potential_to.second] + potential_to.first;
		}
	}
	for (int i = 1; i < N; i++) {
		sort(idx[i].begin(), idx[i].end(), [&](const auto &lhs, const auto &rhs) {
			return V[i][lhs].second < V[i][rhs].second;
		});
		int mn = *min_element(idx[i].begin(), idx[i].end());
		vector<ii> copy_V(V[i].begin(), V[i].end());
		for (int j = 0; j < M[i]; j++) {
			V[i][j] = copy_V[idx[i][j] - mn];
		}
	}
	cin >> Q;
	for (int L, R; Q--; ) {
		cin >> L >> R;
		int lo = 0, hi = M[L] - 1;
		while (hi - lo >= 3) {
			int m1 = lo + (hi - lo) / 3;
			int m2 = hi - (hi - lo) / 3;
			ll f1 = f(idx[L][m1], R - L - 1) + V[L][m1].second - V[L][m1].first;
			ll f2 = f(idx[L][m2], R - L - 1) + V[L][m2].second - V[L][m2].first;
			if (f1 < f2) {
				hi = m2;
			} else {
				lo = m1;
			}
		}
		ll ans = (ll)1e18;
		for (int i = lo; i <= hi; i++) {
			ans = min(ans, f(idx[L][i], R - L - 1) + V[L][i].second - V[L][i].first);
		}
		cout << ans << '\n';
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 64 ms 9644 KB Output is correct
3 Correct 58 ms 13948 KB Output is correct
4 Correct 82 ms 14696 KB Output is correct
5 Correct 62 ms 13908 KB Output is correct
6 Correct 77 ms 14928 KB Output is correct
7 Correct 78 ms 14932 KB Output is correct
8 Correct 67 ms 13928 KB Output is correct
9 Correct 78 ms 14732 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 64 ms 9644 KB Output is correct
3 Correct 58 ms 13948 KB Output is correct
4 Correct 82 ms 14696 KB Output is correct
5 Correct 62 ms 13908 KB Output is correct
6 Correct 77 ms 14928 KB Output is correct
7 Correct 78 ms 14932 KB Output is correct
8 Correct 67 ms 13928 KB Output is correct
9 Correct 78 ms 14732 KB Output is correct
10 Correct 1 ms 6744 KB Output is correct
11 Incorrect 163 ms 15156 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 64 ms 9644 KB Output is correct
3 Correct 58 ms 13948 KB Output is correct
4 Correct 82 ms 14696 KB Output is correct
5 Correct 62 ms 13908 KB Output is correct
6 Correct 77 ms 14928 KB Output is correct
7 Correct 78 ms 14932 KB Output is correct
8 Correct 67 ms 13928 KB Output is correct
9 Correct 78 ms 14732 KB Output is correct
10 Correct 125 ms 22032 KB Output is correct
11 Correct 196 ms 24576 KB Output is correct
12 Correct 214 ms 24320 KB Output is correct
13 Correct 176 ms 23556 KB Output is correct
14 Correct 246 ms 26372 KB Output is correct
15 Correct 229 ms 25424 KB Output is correct
16 Correct 127 ms 23032 KB Output is correct
17 Correct 188 ms 24148 KB Output is correct
18 Correct 81 ms 20264 KB Output is correct
19 Correct 78 ms 19944 KB Output is correct
20 Correct 80 ms 20248 KB Output is correct
21 Correct 77 ms 20212 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 64 ms 9644 KB Output is correct
3 Correct 58 ms 13948 KB Output is correct
4 Correct 82 ms 14696 KB Output is correct
5 Correct 62 ms 13908 KB Output is correct
6 Correct 77 ms 14928 KB Output is correct
7 Correct 78 ms 14932 KB Output is correct
8 Correct 67 ms 13928 KB Output is correct
9 Correct 78 ms 14732 KB Output is correct
10 Correct 1 ms 6744 KB Output is correct
11 Incorrect 163 ms 15156 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Runtime error 33 ms 25436 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 64 ms 9644 KB Output is correct
3 Correct 58 ms 13948 KB Output is correct
4 Correct 82 ms 14696 KB Output is correct
5 Correct 62 ms 13908 KB Output is correct
6 Correct 77 ms 14928 KB Output is correct
7 Correct 78 ms 14932 KB Output is correct
8 Correct 67 ms 13928 KB Output is correct
9 Correct 78 ms 14732 KB Output is correct
10 Correct 1 ms 6744 KB Output is correct
11 Incorrect 163 ms 15156 KB Output isn't correct
12 Halted 0 ms 0 KB -