제출 #1197331

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197331		abczz	Escape Route 2 (JOI24_escape2)	C++20	100 / 100	506 ms	57624 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long

using namespace std;

ll n, q, t, m, a, b, tot, F[300000];
vector <ll> U, W;
vector <array<ll, 2>> tmp;
vector <array<ll, 2>> V[100000];
ll bl[100010][17], br[100010][17], D[100010][2];
vector <array<ll, 3>> Q;
vector <ll> id[100000];
struct SegTree{
  ll st[400000], stid[400000];
  void build(ll id, ll l, ll r) {
    if (l == r) {
      st[id] = V[l].size(), stid[id] = l;
      return;
    }
    ll mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    st[id] = min(st[id*2], st[id*2+1]);
    if (st[id] == st[id*2]) stid[id] = stid[id*2];
    else stid[id] = stid[id*2+1];
  }
  array<ll, 2> query(ll id, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql) return {(ll)1e18, -1};
    else if (ql <= l && r <= qr) return {st[id], stid[id]};
    ll mid = (l+r)/2;
    auto x = query(id*2, l, mid, ql, qr);
    auto y = query(id*2+1, mid+1, r, ql, qr);
    if (x[0] <= y[0]) return x;
    else return y;
  }
}ST;
int main() {
  cin >> n >> t;
  for (int i=0; i<n-1; ++i) {
    cin >> m;
    for (int j=0; j<m; ++j) {
      cin >> a >> b;
      V[i].push_back({a, b});
    }
    sort(V[i].begin(), V[i].end(), [](auto a, auto b) {
      return a[1] < b[1] || (a[1] == b[1] && a[0] < b[0]);
    });
    tmp.clear();
    for (auto [x, y] : V[i]) {
      while (!tmp.empty()) {
        auto [a, b] = tmp.back();
        if (b == y) tmp.pop_back();
        else break;
      }
      if (tmp.empty() || tmp.back()[0] < x) tmp.push_back({x, y});
    }
    swap(V[i], tmp);
  }
  ST.build(1, 0, n-2);
  for (int i=0; i<n-1; ++i) {
    int j = 0;
    for (auto [x, y] : V[i]) {
      id[i].push_back(++tot);
      if (i == 0) bl[id[i].back()][0] = 0, D[id[i].back()][0] = 0;
      else {
        while (j+1 < V[i-1].size()) {
          if (V[i-1][j+1][1] <= x) ++j;
          else break;
        }
        if (V[i-1][j][1] <= x) bl[id[i].back()][0] = id[i-1][j], D[id[i].back()][0] = D[id[i-1][j]][0] + x-V[i-1][j][0];
        else bl[id[i].back()][0] = id[i-1].back(), D[id[i].back()][0] = D[id[i-1].back()][0] + x+t-V[i-1].back()[0];
      }
    }
  }
  for (int i=n-2; i>=0; --i) {
    int j = 0, k = 0;
    for (auto [x, y] : V[i]) {
      if (i == n-2) br[id[i][k]][0] = 0, D[id[i][k]][1] = 0;
      else {
        while (j+1 < V[i+1].size()) {
          if (y > V[i+1][j][0]) ++j;
          else break;
        }
        if (y <= V[i+1][j][0]) br[id[i][k]][0] = id[i+1][j], D[id[i][k]][1] = D[id[i+1][j]][1] + V[i+1][j][1]-y;
        else br[id[i][k]][0] = id[i+1][0], D[id[i][k]][1] = D[id[i+1][0]][1] + V[i+1][0][1]-y+t;
      }
      ++k;
    }
  }
  for (int j=1; j<17; ++j) {
    for (int i=0; i<=tot; ++i) {
      bl[i][j] = bl[bl[i][j-1]][j-1];
      br[i][j] = br[br[i][j-1]][j-1];
    }
  }
  cin >> q;
  for (int i=0; i<q; ++i) {
    cin >> a >> b;
    --a, --b;
    Q.push_back({a, b, i});
  }
  sort(Q.begin(), Q.end());
  for (int query=0; query<q; ++query) {
    a = Q[query][0], b = Q[query][1];
    if (query && a == Q[query-1][0] && b == Q[query-1][1]) {
      F[Q[query][2]] = F[Q[query-1][2]];
      continue;
    }
    auto [d, z] = ST.query(1, 0, n-2, a, b-1);
    U.clear();
    W.clear();
    ll dist = z;
    for (int j=16; j>=0; --j) {
      if (dist - (1LL<<j) >= a) {
        dist -= (1LL<<j);
        U.push_back(j);
      }
    }
    dist = z;
    for (int j=16; j>=0; --j) {
      if (dist + (1LL<<j) <= b-1) {
        dist += (1LL<<j);
        W.push_back(j);
      }
    }
    ll f = 1e18;
    for (int i=0; i<V[z].size(); ++i) {
      ll cur = id[z][i], cur2 = id[z][i];
      for (auto u : U) {
        cur = bl[cur][u];
      }
      for (auto u : W) {
        cur2 = br[cur2][u];
      }
      f = min(f, D[id[z][i]][0]+D[id[z][i]][1]-D[cur][0]-D[cur2][1]+(V[z][i][1]-V[z][i][0]));
    }
    F[Q[query][2]] = f;
  }
  for (int i=0; i<q; ++i) cout << F[i] << '\n';
}

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