| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 984839 | pavement | Escape Route 2 (JOI24_escape2) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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], min_width[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];
min_width[i] = (ll)1e18;
for (int j = 0, a, b; j < M[i]; j++) {
cin >> a >> b;
min_width[i] = min(min_width[i], b - a);
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;
if (L + 1 == R) {
cout << min_width[L] << '\n';
continue;
}
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';
}
}