#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
const int INF = 1e18;
const int N = 4e5 + 5;
vector<array<int,2>> v[N];
void _(){
int n;
cin >> n;
int L[n], R[n];
for(int i = 0; i < n; i++){
cin >> L[i] >> R[i];
--L[i], --R[i];
}
for(int i = n - 1; i; --i){
v[i * 2].push_back({i, 0});
v[i * 2 + 1].push_back({i, 0});
}
for(int i = 0; i < n; i++){
int l = L[i] + n, r = R[i] + n + 1;
for(; l < r; l >>= 1, r >>= 1){
if(l&1) v[l++].push_back({i + n, 1});
if(r&1) v[--r].push_back({i + n, 1});
}
}
vector<int> dist1(2 * n, INF), distn(2 * n, INF);
dist1[n] = 0;
deque<int> dq;
dq.push_back(n);
while(!dq.empty()){
int c = dq.front();
dq.pop_front();
for(auto [u, w] : v[c]){
if(w == 0 && dist1[c] < dist1[u]){
dist1[u] = dist1[c];
dq.push_front(u);
}
if(w == 1 && dist1[c] + 1 < dist1[u]){
dist1[u] = dist1[c] + 1;
dq.push_back(u);
}
}
}
dist1[n] = 1;
distn[2 * n - 1] = 0;
dq.push_back(2 * n - 1);
while(!dq.empty()){
int c = dq.front();
dq.pop_front();
for(auto [u, w] : v[c]){
if(w == 0 && distn[c] < distn[u]){
distn[u] = distn[c];
dq.push_front(u);
}
if(w == 1 && distn[c] + 1 < distn[u]){
distn[u] = distn[c] + 1;
dq.push_back(u);
}
}
}
distn[2 * n - 1] = 1;
vector<int> dist1n(2 * n, INF);
for(int i = n; i < 2 * n; i++){
dist1n[i] = dist1[i] + distn[i] - 1;
dq.push_back(i);
}
while(!dq.empty()){
int c = dq.front();
dq.pop_front();
for(auto [u, w] : v[c]){
if(w == 0 && dist1n[c] < dist1n[u]){
dist1n[u] = dist1n[c];
dq.push_front(u);
}
if(w == 1 && dist1n[c] + 1 < dist1n[u]){
dist1n[u] = dist1n[c] + 1;
dq.push_back(u);
}
}
}
int q;
cin >> q;
while(q--){
int c; cin >> c;
--c;
if(dist1n[c + n] == INF) cout << -1 << '\n';
else cout << dist1n[c + n] << '\n';
}
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |