Submission #1052393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052393		erray	Escape Route 2 (JOI24_escape2)	C++17	54 / 100	3065 ms	30760 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/hp/contests/joi24scd4/debug.h"
#else 
  #define debug(...) void(37)
#endif

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N, T;
  cin >> N >> T;
  vector<vector<array<int, 2>>> g(N);
  for (int i = 0; i < N - 1; ++i) {
    int M;
    cin >> M;
    vector<int> A(M), B(M);
    for (int j = 0; j < M; ++j) {
      cin >> A[j] >> B[j];
    }
    vector<int> ord(M);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int x, int y) {
      return A[x] < A[y];
    });
    vector<int> st;
    for (auto x:  ord) {
      while (!st.empty() && B[st.back()] >= B[x]) {
        st.pop_back();
      }
      st.push_back(x);
    }
    for (auto x : st) {
      g[i].push_back({A[x], B[x]});
    }
  }
  vector<int> pref(N + 1);
  vector<array<int, 2>> info;
  for (int i = 0; i < N; ++i) {
    pref[i + 1] = pref[i] + int(g[i].size());
    for (auto x : g[i]) {
      info.push_back(x);
    }
  }
  debug(g, pref, info);
  auto Id = [&](int i, int j) {
    assert(j < int(g[i].size()));
    return pref[i] + j;
  };
  auto Next = [&](int i, int t) -> array<int, 2> {
    int ind = lower_bound(g[i].begin(), g[i].end(), array<int, 2>{t, -1}) - g[i].begin();
    if (ind == int(g[i].size())) {
      return {0, 1};
    } else {
      return {ind, 0};
    }
  };
  
  int s = pref[N];
  int LG = __lg(N) + 1;
  vector<vector<int>> lift(LG, vector<int>(s, -1));
  vector<vector<int>> cost(LG, vector<int>(s));
  for (int i = 0; i < N - 2; ++i) {
    for (int j = 0; j < int(g[i].size()); ++j) {
      auto[to, _cost] = Next(i + 1, g[i][j][1]);
      lift[0][Id(i, j)] = Id(i + 1, to);
      cost[0][Id(i, j)] = _cost;
    }
  }
  for (int l = 1; l < LG; ++l) {
    for (int i = 0; i < s; ++i) {
      int to = lift[l - 1][i];
      if (to == -1) {
        lift[l][i] = -1;
      } else {
        lift[l][i] = lift[l - 1][to];
        cost[l][i] = cost[l - 1][i] + cost[l - 1][to];
      }
    }
  }
  auto Find_dist = [&](int v, int dist) -> int64_t {
    int days = 0;
    int start = info[v][0];
    for (int i = 0; dist > 0; ++i, dist >>= 1) {
      if (dist % 2) {
        days += cost[i][v];
        v = lift[i][v];
      }
    }
    return 1LL * days * T + info[v][1] - start;
  };
  
  debug(lift, cost);
  int Q;
  cin >> Q;
  while (Q--) {
    int L, R;
    cin >> L >> R;
    --L, --R;
    int64_t ans = int64_t(1e18);
    for (int j = 0; j < int(g[L].size()); ++j) {
      ans = min(ans, Find_dist(Id(L, j), R - L - 1));
    }
    cout << ans << '\n';
  }
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 17 / 17
• Subtask 4: 23 / 23
• Subtask 5: 0 / 36
• Subtask 6: 0 / 10