Submission #1192874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192874		joelgun14	Escape Route 2 (JOI24_escape2)	C++20	54 / 100	3095 ms	183400 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define endl "\n"
#define ll long long
#define mp make_pair
#define ins insert
#define lb lower_bound
#define pb push_back
#define ub upper_bound
#define lll __int128
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
int main() {
  ios_base::sync_with_stdio(0); cin.tie(NULL);
  int n, t;
  cin >> n >> t;
  // fi -> (city, next flight idx)
  // se -> (time of arrival, time elapsed)
  // each city has different number of flights
  vector<pair<pair<ll, ll>, pair<ll, ll>>> nxt[17][n + 1];
  vector<pair<ll, ll>> flights[n + 1];
  for (ll i = 1; i < n; ++i) {
    ll m;
    cin >> m;
    vector<pair<ll, ll>> a;
    for (ll i = 1; i <= m; ++i) {
      ll x, y;
      cin >> x >> y;
      a.pb(mp(x, y));
    }
    sort(a.begin(), a.end());
    priority_queue<pair<ll, ll>> pq;
    vector<pair<ll, ll>> res;
    for (auto [l, r] : a) {
      while (pq.size() && pq.top().fi < l) {
        res.push_back(mp(pq.top().se, pq.top().fi));
        pq.pop();
      }
      while (pq.size() && pq.top().fi >= r) {
        pq.pop();
        while (pq.size() && pq.top().fi < l) {
          res.push_back(mp(pq.top().se, pq.top().fi));
          pq.pop();
        }
      }
      pq.push({r, l});
    }
    while (pq.size()) {
      res.push_back(mp(pq.top().se, pq.top().fi));
      pq.pop();
    }
    sort(res.begin(), res.end());
    flights[i] = res;
  }
  for(ll i = n - 1; i >= 1; --i) {
    for (ll j = 0; j < 17; ++j) {
      nxt[j][i].resize(flights[i].size() + 1);
    }
    for (ll j = 0; j < 17; ++j) {
      for (ll k = 0; k < flights[i].size(); ++k) {
        if (j == 0) {
          nxt[j][i][k] = mp(mp(i + 1, lb(flights[i + 1].begin(), flights[i + 1].end(), mp(flights[i][k].se, 0ll)) - flights[i + 1].begin()), mp(flights[i][k].se, flights[i][k].se - flights[i][k].fi));
          // cerr << "DEB2 " << i << " " << k << " " << nxt[j][i][k].fi.fi << " " << nxt[j][i][k].fi.se << " " << nxt[j][i][k].se.fi << " " << nxt[j][i][k].se.se << endl;
        } else {
          auto [city, idx] = nxt[j - 1][i][k].fi;
          auto [toa, elapsed] = nxt[j - 1][i][k].se;
          if (city == n || city == 0) {
            // cerr << "NXT " << j << " " << i << " " << k << " " << city << endl;
            continue;
          }
          if (idx == flights[city].size()) {
            elapsed += t - toa + flights[city][0].fi;
            idx = 0;
          } else {
            elapsed += flights[city][idx].fi - toa;
          }
          nxt[j][i][k] = mp(nxt[j - 1][city][idx].fi, mp(nxt[j - 1][city][idx].se.fi, elapsed + nxt[j - 1][city][idx].se.se));
          // cerr << "DEB3 " << j << " " << i << " " << k << " " << nxt[j - 1][city][idx].fi.fi << " " << nxt[j - 1][city][idx].fi.se << endl;
        }
      }
    }
  }

  // cerr << "HERE" << endl;

  ll q;
  cin >> q;
  while (q--) {
    ll l, r;
    cin >> l >> r;
    // binlift from l to r
    ll ans = 4e18;
    for (ll init = 0; init < flights[l].size(); ++init) {
      ll res = 0;
      ll pos = l, idx = init;
      for (ll i = 16; i >= 0; --i) {
        if (nxt[i][pos][idx].fi.fi > 0 && nxt[i][pos][idx].fi.fi < r) {
          // cerr << "HERE" << endl;
          // cerr << i << " " << pos << " " << idx << " " << nxt[i][pos].size() << endl;
          res += nxt[i][pos][idx].se.se;
          pair<pair<ll, ll>, pair<ll, ll>> tmp = nxt[i][pos][idx];
          pos = tmp.fi.fi;
          idx = tmp.fi.se;
          auto [toa, elapsed] = tmp.se;
          // cerr << toa << " " << elapsed << endl;
          // cerr << "GOT VALUE" << endl;
          if (idx == flights[pos].size()) {
            // cerr << "HERE" << endl;
            // cerr << pos << " " << flights[pos].size() << endl;
            res += t - toa + flights[pos][0].fi;
            idx = 0;
          } else {
            res += flights[pos][idx].fi - toa;
          }
        }
      }
      // cerr << "NEW VALUE: " << 0 << " " << pos << " " << idx << endl;
      ans = min(ans, res + nxt[0][pos][idx].se.se);
    }
    cout << ans << endl;
  }
  return 0;
}

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