Submission #803099

#TimeUsernameProblemLanguageResultExecution timeMemory
803099lukameladzePassport (JOI23_passport)C++17
100 / 100
678 ms88028 KiB
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair <int,int>
#define pb push_back
const int N = 3e5 + 5;
int n, l[N], r[N];
pii tree[4 * N];
multiset <pii> ms[4 * N];
void update(int node, int le, int ri, int idx, int val, int id) {
  if (le > idx || ri < idx) return ;
  if (le == ri) {
    // cout<<"upd "<<le<<" "<<ri<<" "<<node<<"\n";
    if (val == 0) {
      if (!ms[node].size()) {
        // cout<<node<<" "<<idx<<" "<<val<<" "<<id<<"\n";
        // exit(0);
        assert(false);
      }
      assert(ms[node].size());
      ms[node].erase(--ms[node].end());
      if (!ms[node].size()) {
        tree[node] = {0, 0}; return ;
      }
    } 
    if (val != 0) ms[node].insert({val, id});
    auto it = --ms[node].end();
    tree[node] = {(*it).f, (*it).s};
    return ;
  }
  int mid = (le + ri) / 2;
  update(2 * node, le, mid, idx, val, id);
  update(2 * node + 1, mid + 1, ri, idx, val, id);
  tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}
pii getans(int node, int le, int ri, int start, int end) {
  if (le > end || ri < start) return {0, 0};
  if (le >= start && ri <= end) return tree[node];
  int mid = (le + ri) / 2;
  return max(getans(2 * node, le, mid, start, end), getans(2 * node + 1, mid + 1, ri ,start, end));
}
int dp[2][N];
void bfs(int a, int ty) {
  for (int i = 0; i < 4 * N; i++) {
    tree[i] = {0, 0}; 
    ms[i].clear();
  }
  for (int i = 1; i <= n; i++) {
    if (i == a) continue;
    dp[ty][i] = 1e9;
    update(1, 1, n, l[i], r[i], i);
  }

  queue <int> q;
  q.push(a);
  dp[ty][a] = 0;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    while (getans(1, 1, n, 1, x).f >= x) {
      pii sth = getans(1, 1, n, 1, x);
      q.push(sth.s);
      dp[ty][sth.s] = dp[ty][x] + 1;
      update(1, 1, n, l[sth.s], 0, sth.s);
    }
  }
}

int tree_mn[4 * N];
void upd_mn(int node, int le, int ri, int idx, int val) {
  if (le > idx || ri < idx) return ;
  if (le == ri) {
    tree_mn[node] = val; return ;
  }
  int mid = (le + ri) / 2;
  upd_mn(2 * node, le, mid, idx,val);
  upd_mn(2 * node + 1, mid + 1, ri, idx,val);
  tree_mn[node] = min(tree_mn[2 * node], tree_mn[2 * node + 1]);
}
int get_mn(int node, int le, int ri, int start, int end) {
  if (le > end || ri < start) return 1e9;
  if (le >= start && ri <= end) return tree_mn[node];
  int mid = (le + ri) / 2;
  return min(get_mn(2 * node, le ,mid, start, end), get_mn(2 * node + 1, mid + 1, ri, start, end));
}
signed main() {
  std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  cin>>n;
  for (int i = 1; i <= n; i++) {
    cin>>l[i]>>r[i];
  }
  bfs(1, 0);
  bfs(n, 1);
  vector <pii> vec;
  for (int i = 1; i <= n; i++) {
    vec.pb({dp[0][i] + dp[1][i] - (i != 1 && i != n), i});
  }
  sort(vec.begin(), vec.end());
  for (pii sth : vec) {
    upd_mn(1, 1, n, sth.s, sth.f);
  }
  vector <int> res(n + 5, 0);
  for (int i = 0; i < (int)vec.size(); i++) {
    int id = vec[i].s;
    res[id] = min(vec[i].f, get_mn(1, 1, n, l[id], r[id]) + 1);
    upd_mn(1, 1, n, id, res[id]);
  }
  int q;
  cin>>q;
  while(q--) {
    int idx; cin>>idx;
    cout<<(res[idx] >= 1e9 ? -1 : res[idx])<<"\n";
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...