Submission #1151420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151420		horiseun	Passport (JOI23_passport)	C++20	100 / 100	564 ms	141432 KiB

passport

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n, q, offset, mp[200005];
vector<pair<int, int>> adj[1000005];

void build(int curr, int l, int r) {
  if (l + 1 == r) {
    offset = max(offset, curr);
    mp[l] = curr;
    return;
  }
  adj[2 * curr].emplace_back(curr, 0);
  adj[2 * curr + 1].emplace_back(curr, 0);
  build(2 * curr, l, (l + r) / 2);
  build(2 * curr + 1, (l + r) / 2, r);
}

void update(int curr, int l, int r, int ql, int qr, int x) {
  if (qr <= l || r <= ql) return;
  if (ql <= l && r <= qr) {
    adj[curr].emplace_back(x, 1);
    // cout << "added " << x << " " << curr << "\n";
    return;
  }
  update(2 * curr, l, (l + r) / 2, ql, qr, x);
  update(2 * curr + 1, (l + r) / 2, r, ql, qr, x);
}

void dijkstra(int strt, vector<int> &dist) {
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  dist[strt] = 0;
  pq.emplace(0, strt);
  while (!pq.empty()) {
    int cdist = pq.top().first, curr = pq.top().second;
    pq.pop();
    if (cdist > dist[curr]) continue;
    for (auto [x, d] : adj[curr]) {
      if (dist[curr] + d < dist[x]) {
        dist[x] = dist[curr] + d;
        pq.emplace(dist[x], x);
      }
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n;
  build(1, 1, n + 1);
  offset++;
  for (int i = 1; i <= n; i++) {
    int l, r; cin >> l >> r;
    update(1, 1, n + 1, l, r + 1, mp[i]);
  }
  vector<int> dist1(5 * n + 5, 2e9), distn(5 * n + 5, 2e9);
  dijkstra(mp[1], dist1);
  dijkstra(mp[n], distn);
  for (int i = 1; i <= n; i++) {
    adj[offset].emplace_back(mp[i], dist1[mp[i]] + distn[mp[i]] - (i != 1 && i != n));
  }
  vector<int> dist(5 * n + 5, 2e9);
  dijkstra(offset, dist);
  cin >> q;
  while (q--) {
    int x; cin >> x;
    cout << (dist[mp[x]] >= 2e9 ? -1 : dist[mp[x]]) << "\n";
  }
}

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