Submission #1038764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038764		juicy	Passport (JOI23_passport)	C++17	100 / 100	492 ms	81920 KiB

passport

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5, inf = 1e9 + 7;

int n, q;
int res[4 * N], pos[N], d[4 * N], vis[4 * N];
vector<array<int, 2>> g[4 * N];

void bfs(int src) {
  memset(d, 0x3f, sizeof(d));
  deque<int> q;
  d[src] = 0;
  q.push_back(src);
  while (q.size()) {
    int u = q.front(); q.pop_front();
    if (vis[u] == src) {
      continue;
    }
    vis[u] = src;
    for (auto [v, w] : g[u]) {
      if (d[v] > d[u] + w) {
        d[v] = d[u] + w;
        if (w) {
          q.push_back(v);
        } else {
          q.push_front(v);
        }
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    if (res[pos[i]] != inf && d[pos[i]] < inf) {
      res[pos[i]] += d[pos[i]];
    } else {
      res[pos[i]] = inf;
    }
  }
}

void add(int u, int v, int w) {
  g[v].push_back({u, w});
}

void bld(int id = 1, int l = 1, int r = n) {
  if (l == r) {
    pos[l] = id;
    return;
  }
  res[id] = inf;
  int md = (l + r) / 2;
  bld(id * 2, l, md);
  bld(id * 2 + 1, md + 1, r);
  add(id, id * 2, 0);
  add(id, id * 2 + 1, 0);
}

void upd(int u, int v, int x, int id = 1, int l = 1, int r = n) {
  if (u <= l && r <= v) {
    add(x, id, 1);
    return;
  }
  int md = (l + r) / 2;
  if (u <= md) {
    upd(u, v, x, id * 2, l, md);
  }
  if (md < v) {
    upd(u, v, x, id * 2 + 1, md + 1, r);
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n;
  bld();
  for (int i = 1; i <= n; ++i) {
    int l, r; cin >> l >> r;
    upd(l, r, pos[i]);
  }
  bfs(pos[1]);
  bfs(pos[n]);
  using T = array<int, 2>;
  priority_queue<T, vector<T>, greater<T>> pq;
  for (int i = 1; i <= n; ++i) {
    if (res[pos[i]] != inf) {
      if (i != 1 && i != n) {
        res[pos[i]] -= 1;
      }
      pq.push({res[pos[i]], pos[i]});
    }
  }
  while (pq.size()) {
    auto [c, u] = pq.top(); pq.pop();
    if (c != res[u]) {
      continue;
    }
    for (auto [v, w] : g[u]) {
      if (res[v] > res[u] + w) {
        pq.push({res[v] = res[u] + w, v});
      }
    }
  }
  cin >> q;
  while (q--) {
    int u; cin >> u;
    cout << (res[pos[u]] == inf ? -1 : res[pos[u]]) << "\n";
  }
  return 0;
}

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