Submission #984854

#TimeUsernameProblemLanguageResultExecution timeMemory
984854pavementEscape Route 2 (JOI24_escape2)C++17
23 / 100
214 ms31596 KiB
#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], min_width[100005], anc[25][100005]; ll dep[100005]; vector<int> idx[100005]; vector<ii> V[100005], rngs[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]; } ll is(ii a, ii b, int lim) { int lo = 0, hi = lim, ret = (int)1e9; while (lo <= hi) { int mid = (lo + hi) / 2; if (f(a.first, mid) + a.second <= f(b.first, mid) + b.second) { ret = mid; hi = mid - 1; } else { lo = mid + 1; } } return ret; } 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] = 2e9; 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++) { assert(!V[i + 1].empty()); 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++) { int mn = *min_element(idx[i].begin(), idx[i].end()); sort(idx[i].begin(), idx[i].end(), [&](const auto &lhs, const auto &rhs) { return V[i][lhs - mn].second > V[i][rhs - mn].second; }); 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]; while (rngs[i].size() > 1 && is(rngs[i][rngs[i].size() - 1], mp(idx[i][j], V[i][j].second - V[i][j].first), N - i - 1) <= is(rngs[i][rngs[i].size() - 2], rngs[i][rngs[i].size() - 1], N - i - 1)) { rngs[i].pop_back(); } rngs[i].eb(idx[i][j], V[i][j].second - V[i][j].first); } } cin >> Q; for (int L, R; Q--; ) { cin >> L >> R; if (L + 1 == R) { cout << min_width[L] << '\n'; continue; } ll ans = (ll)1e18; for (auto [x, y] : rngs[L]) { ans = min(ans, f(x, R - L - 1) + y); } cout << ans << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...