Submission #883862

#	Time	Username	Problem	Language	Result	Execution time	Memory
883862		vjudge1	Passport (JOI23_passport)	C++17	100 / 100	472 ms	49652 KiB

passport

// author: erray
#include <bits/stdc++.h>

#ifdef DEBUG
  #include "debug.h"
#else
  #define debug(...) void(37)
#endif

using namespace std;

struct SegmentExtractor {
  vector<vector<int>> segs;
  int n;
  SegmentExtractor(int _n) : n(_n) {
    segs.resize(n << 1);
  }
  void push(int l, int r, int id) {
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) segs[l++].push_back(id);
      if (r & 1) segs[--r].push_back(id);
    }
  } 
  template<typename F>
  void extract(int p, F op) {
    for (p += n; p > 0; p >>= 1) {
      for (auto x : segs[p]) {
        op(x);
      }
      segs[p].clear();
    }
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<int> L(N), R(N);
  for (int i = 0; i < N; ++i) {
    cin >> L[i] >> R[i];
    --L[i], --R[i];
  }
  auto Bfs = [&](vector<array<int, 2>> sources) {
    debug(sources);
    vector<int> dist(N, -1);
    vector<vector<int>> que(N + 1);
    SegmentExtractor st(N);
    for (auto[v, d] : sources) {
      if (d <= N) {
        dist[v] = d;
        que[d].push_back(v); 
      }
    }
    for (int i = 0; i < N; ++i) {
      st.push(L[i], R[i], i);
    }
    for (int d = 0; d < N; ++d) {
      for (auto v : que[d]) {
        if (dist[v] < d) {
          continue;
        }
        st.extract(v, [&](int u) {
          if (dist[u] == -1 || dist[u] > d + 1) {
            dist[u] = d + 1;
            que[d + 1].push_back(u);
          } 
        });
      }
    }
    return dist;
  };
  auto dist_L = Bfs(vector<array<int, 2>>{array<int, 2>{0, 0}});
  auto dist_R = Bfs(vector<array<int, 2>>{array<int, 2>{N - 1, 0}});  
  debug(dist_L, dist_R);
  vector<array<int, 2>> sources;
  for (int i = 0; i < N; ++i) {
    if (dist_L[i] != -1 && dist_R[i] != -1) {
      sources.push_back({i, dist_L[i] + dist_R[i] - (i != 0 && i != N - 1)});
    } 
  }
  auto dist = Bfs(sources);
  debug(dist);
  int Q;
  cin >> Q;
  while (Q--) {
    int X;
    cin >> X;
    --X;
    cout << (dist[X] == -1 ? -1 : dist[X]) << '\n';
  }
}

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 46 / 46