Submission #988050

#	Time	Username	Problem	Language	Result	Execution time	Memory
988050		rxlfd314	Escape Route 2 (JOI24_escape2)	C++17	100 / 100	1022 ms	73292 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

constexpr int mxN = 100000;
int N, T, Q, L[3*mxN], R[3*mxN], same[3*mxN], uf[mxN], lft[mxN], rht[mxN];
vt<ari2> ltr[mxN], rtl[mxN], all_flights;
set<ari2> adj[mxN*2];
vt<int> nodes[mxN];
ll lz[mxN], ans[3*mxN], tot[mxN];

int find(int i) {
  return uf[i] < 0 ? i : uf[i] = find(uf[i]);
}

void unite(int a, int b) {
  a = find(a), b = find(b);
  if (a == b)
    assert(false);
  if (uf[a] > uf[b])
    swap(a, b);
  uf[a] += uf[b];
  uf[b] = a;
  for (int j : nodes[b]) {
    nodes[a].push_back(j);
    tot[j] += lz[b] - lz[a];
  }
  nodes[b].clear();
};

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cin >> N >> T;
  FOR(i, 0, N-2) {
    int m;
    cin >> m;
    vt<ari2> v(m);
    for (auto &[a, b] : v)
      cin >> a >> b;
    sort(all(v), [&](const ari2 &a, const ari2 &b) {
      return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
    });
    vt<ari2> nf;
    for (auto &[a, b] : v) {
      while (size(nf) && nf.back()[1] >= b)
        nf.pop_back();
      nf.push_back({a, b});
    }
    lft[i] = size(all_flights);
    for (auto &vv : nf)
      all_flights.push_back(vv);
    rht[i] = size(all_flights) - 1;
  }

  cin >> Q;
  iota(same, same+Q, 0);
  FOR(i, 0, Q-1) {
    int &a = L[i], &b = R[i];
    cin >> a >> b, a--, b--;
    auto it = adj[a].lower_bound({b+N, 0});
    if (it != end(adj[a]) && (*it)[0] == b+N) {
      same[i] = (*it)[1];
      continue;
    }
    adj[a].insert({b+N, i});
    adj[b+N].insert({a, i});
  }
  /* generate queries */ {
    multiset<ari2> ms;
    FOR(i, 0, 2*N-1)
      if (size(adj[i]))
        ms.insert({size(adj[i]), i});
    while (size(ms)) {
      auto [d, i] = *begin(ms);
      ms.erase(begin(ms));
      for (auto [j, qi] : adj[i]) {
        ms.erase(ms.find({size(adj[j]), j}));
        adj[j].erase(adj[j].find({i, qi}));
        if (size(adj[j]))
          ms.insert({size(adj[j]), j});
        if (i < j)
          ltr[j-N].push_back({i, qi});
        else
          rtl[N-1-j].push_back({N-1-i+N, qi});
      }
    }
  }
  
  fill(ans, ans+Q, LLONG_MAX);
  vt<bool> marked(Q);
  FOR(_, 1, 2) {
    memset(uf, -1, sizeof(uf));
    memset(lz, 0, sizeof(lz));
    memset(tot, 0, sizeof(tot));
    FOR(i, 0, size(all_flights)-1)
      nodes[i].push_back(i);
    FOR(ii, 0, N-2) {
      if (ii > 0) {
        int j = lft[ii];
        FOR(i, lft[ii-1], rht[ii-1]) {
          auto [a, b] = all_flights[i];
          for (; j <= rht[ii] && all_flights[j][0] < b; j++);
          int k = j > rht[ii] ? lft[ii] : j;
          auto [c, d] = all_flights[k];
          lz[find(i)] += ((c - b) % T + T) % T;
          unite(i, k);
        }
      }
      FOR(i, lft[ii], rht[ii])
        lz[find(i)] += all_flights[i][1] - all_flights[i][0];
      for (auto [l, qi] : ltr[ii+1]) {
        marked[qi] = true;
        FOR(j, lft[l], rht[l])
          ans[qi] = min(ans[qi], lz[find(j)] + tot[j]);
      }
    }
    if (_ == 2)
      break;
    for (auto &[a, b] : all_flights) {
      a *= -1, b *= -1;
      swap(a, b);
    }
    FOR(i, 0, size(all_flights)-1)
      nodes[i].clear();
    reverse(all(all_flights));
    for (int i = 0, j = N-2; i <= j; i++, j--) {
      lft[i] = size(all_flights) - 1 - lft[i];
      rht[i] = size(all_flights) - 1 - rht[i];
      if (i < j) {
        lft[j] = size(all_flights) - 1 - lft[j];
        rht[j] = size(all_flights) - 1 - rht[j];
        swap(lft[i], lft[j]);
        swap(rht[i], rht[j]);
        swap(lft[i], rht[i]);
      }
      swap(lft[j], rht[j]);
    }
    FOR(i, 0, N-1)
      swap(ltr[i], rtl[i]);
  }

  FOR(i, 0, Q-1) {
    cout << ans[same[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