oj.uz

Submission #984836

# Submission time Handle Problem Language Result Execution time Memory
984836 2024-05-17T06:47:16 Z pavement Escape Route 2 (JOI24_escape2) C++17
23 / 100
 239 ms 25404 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 = 20; j >= 0; j--) {
		if (k & (1 << j)) {
			v = anc[j][v];
		}
	}
	assert(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 54 ms 9608 KB Output is correct
3 Correct 62 ms 13908 KB Output is correct
4 Correct 78 ms 14884 KB Output is correct
5 Correct 63 ms 13820 KB Output is correct
6 Correct 80 ms 14928 KB Output is correct
7 Correct 77 ms 14932 KB Output is correct
8 Correct 60 ms 14052 KB Output is correct
9 Correct 77 ms 14864 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 54 ms 9608 KB Output is correct
3 Correct 62 ms 13908 KB Output is correct
4 Correct 78 ms 14884 KB Output is correct
5 Correct 63 ms 13820 KB Output is correct
6 Correct 80 ms 14928 KB Output is correct
7 Correct 77 ms 14932 KB Output is correct
8 Correct 60 ms 14052 KB Output is correct
9 Correct 77 ms 14864 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 102 ms 14248 KB Output is correct
12 Correct 102 ms 14204 KB Output is correct
13 Correct 98 ms 14172 KB Output is correct
14 Correct 98 ms 14352 KB Output is correct
15 Correct 90 ms 14752 KB Output is correct
16 Correct 74 ms 9568 KB Output is correct
17 Runtime error 11 ms 21872 KB Execution killed with signal 11
18 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 54 ms 9608 KB Output is correct
3 Correct 62 ms 13908 KB Output is correct
4 Correct 78 ms 14884 KB Output is correct
5 Correct 63 ms 13820 KB Output is correct
6 Correct 80 ms 14928 KB Output is correct
7 Correct 77 ms 14932 KB Output is correct
8 Correct 60 ms 14052 KB Output is correct
9 Correct 77 ms 14864 KB Output is correct
10 Correct 124 ms 21104 KB Output is correct
11 Correct 210 ms 24020 KB Output is correct
12 Correct 239 ms 23900 KB Output is correct
13 Correct 167 ms 22904 KB Output is correct
14 Correct 219 ms 23944 KB Output is correct
15 Correct 233 ms 23828 KB Output is correct
16 Correct 145 ms 21016 KB Output is correct
17 Correct 205 ms 23824 KB Output is correct
18 Correct 96 ms 20048 KB Output is correct
19 Correct 74 ms 19960 KB Output is correct
20 Correct 79 ms 20184 KB Output is correct
21 Correct 80 ms 20128 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 54 ms 9608 KB Output is correct
3 Correct 62 ms 13908 KB Output is correct
4 Correct 78 ms 14884 KB Output is correct
5 Correct 63 ms 13820 KB Output is correct
6 Correct 80 ms 14928 KB Output is correct
7 Correct 77 ms 14932 KB Output is correct
8 Correct 60 ms 14052 KB Output is correct
9 Correct 77 ms 14864 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 102 ms 14248 KB Output is correct
12 Correct 102 ms 14204 KB Output is correct
13 Correct 98 ms 14172 KB Output is correct
14 Correct 98 ms 14352 KB Output is correct
15 Correct 90 ms 14752 KB Output is correct
16 Correct 74 ms 9568 KB Output is correct
17 Runtime error 11 ms 21872 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Runtime error 34 ms 25404 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 54 ms 9608 KB Output is correct
3 Correct 62 ms 13908 KB Output is correct
4 Correct 78 ms 14884 KB Output is correct
5 Correct 63 ms 13820 KB Output is correct
6 Correct 80 ms 14928 KB Output is correct
7 Correct 77 ms 14932 KB Output is correct
8 Correct 60 ms 14052 KB Output is correct
9 Correct 77 ms 14864 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 102 ms 14248 KB Output is correct
12 Correct 102 ms 14204 KB Output is correct
13 Correct 98 ms 14172 KB Output is correct
14 Correct 98 ms 14352 KB Output is correct
15 Correct 90 ms 14752 KB Output is correct
16 Correct 74 ms 9568 KB Output is correct
17 Runtime error 11 ms 21872 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -