Submission #894229

#	Time	Username	Problem	Language	Result	Execution time	Memory
894229		box	Passport (JOI23_passport)	C++17	100 / 100	1031 ms	93612 KiB

passport

#include "bits/stdc++.h"
using namespace std;
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)
 
#define ar array
#define all(v) (v).begin(), (v).end()
#define sz(v) static_cast<int>(v.size())
typedef vector<int> vi;
typedef long long ll;
 
const int N = 2e5, N_ = 1 << 18;
 
int n_;
vector<pair<int, int>> g[N_ * 2 + N];
 
vi getSegs(int l, int r) {
  vi v;
  for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
    if (l & 1) v.push_back(l++);
    if (~r & 1) v.push_back(r--);
  }
  return v;
}
 
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin.exceptions(cin.failbit);
  int n;
  cin >> n;
  n_ = 1;
  while (n_ < n) n_ <<= 1;
  F0R(i, n) {
    int l, r;
    cin >> l >> r, l--, r--;
    g[n_ * 2 + i].push_back({n_ + i, 1});
    for (int v : getSegs(l, r)) g[v].push_back({n_ * 2 + i, 0});
  }
  FOR(i, 1, n_) {
    g[i << 1 | 0].push_back({i, 0});
    g[i << 1 | 1].push_back({i, 0});
  }
  static int d1[N_ * 2 + N], dn[N_ * 2 + N], d[N_ * 2 + N];
  FOR(i, 1, n_ * 2 + n)
  d1[i] = dn[i] = d[i] = N_;
  priority_queue<pair<int, int>> pq;
  pq.push({-(d1[n_ + 0] = 0), n_ + 0});
  while (sz(pq)) {
    auto [d_, i] = pq.top();
    pq.pop();
    d_ *= -1;
    if (d_ != d1[i]) continue;
    for (auto [j, w] : g[i])
      if (d1[i] + w < d1[j]) pq.push({-(d1[j] = d1[i] + w), j});
  }
  pq.push({-(dn[n_ + n - 1] = 0), n_ + n - 1});
  while (sz(pq)) {
    auto [d_, i] = pq.top();
    pq.pop();
    d_ *= -1;
    if (d_ != dn[i]) continue;
    for (auto [j, w] : g[i])
      if (dn[i] + w < dn[j]) pq.push({-(dn[j] = dn[i] + w), j});
  }
  FOR(i, 1, n_ * 2 + n) {
    d[i] = min(d[i], d1[i] + dn[i]);
    pq.push({-d[i], i});
  }
  while (sz(pq)) {
    auto [d_, i] = pq.top();
    pq.pop();
    d_ *= -1;
    if (d_ != d[i]) continue;
    for (auto [j, w] : g[i])
      if (d[i] + w < d[j]) pq.push({-(d[j] = d[i] + w), j});
  }
  int q;
  cin >> q;
  F0R(h, q) {
    int i;
    cin >> i, i--;
    cout << (d[n_ + i] == N_ ? -1 : d[n_ + i]) << '\n';
  }
}

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