#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#include <stack>
using namespace std;
#define int long long
#define mp make_pair
#define fi first
#define pii pair<int,int>
#define se second
const int INF=1000000000000000000;
//const int INF=1e9;
const int N=1000000;
//const int M=998244353;
const int ln=20;
template<typename T>
std::ostream& operator<< (std::ostream& os,pair<T,T> p){
return os << p.fi << "," << p.se << " ";
}
void solve(){
int n;
cin >> n;
int l[n];
int r[n];
for(int i=0;i<n;i++){
cin >> l[i] >> r[i];
l[i]--,r[i]--;
}
vector<pii> edges[2*n];
for(int i=n-1;i>0;i--){
edges[2*i].push_back(mp(i,0));
edges[2*i+1].push_back(mp(i,0));
}
for(int i=0;i<n;i++){
int li=l[i]+n;
int ri=r[i]+n+1;
//cout << li << " " << ri << "?\n";
while(li<ri){
if(li&1){
//cout << li << " " << i+n << "\n";
edges[li].push_back(mp(i+n,1));
li++;
}
if(ri&1){
ri--;
edges[ri].push_back(mp(i+n,1));
//cout << ri << " " << i+n << "\n";
}
li>>=1;
ri>>=1;
}
}
int dist1[2*n];
int distn[2*n];
for(int i=0;i<2*n;i++){
dist1[i]=distn[i]=INF;
}
{
dist1[n]=0;
priority_queue<pii,vector<pii>,greater<pii>> pq;
pq.push(mp(dist1[n],n));
while(!pq.empty()){
auto [w,u]=pq.top();
pq.pop();
if(w!=dist1[u]) continue;
for(auto [v,w1]:edges[u]){
if(dist1[v]>w+w1){
dist1[v]=w+w1;
pq.push(mp(dist1[v],v));
}
}
}
}
for(int i=0;i<2*n;i++){
if(dist1[i]==0) dist1[i]++;
//cout << dist1[i] << "\n";
}
{
distn[2*n-1]=0;
priority_queue<pii,vector<pii>,greater<pii>> pq;
pq.push(mp(distn[2*n-1],2*n-1));
while(!pq.empty()){
auto [w,u]=pq.top();
pq.pop();
if(w!=distn[u]) continue;
for(auto [v,w1]:edges[u]){
if(distn[v]>w+w1){
distn[v]=w+w1;
pq.push(mp(distn[v],v));
}
}
}
distn[2*n-1]++;
}
for(int i=0;i<2*n;i++){
if(distn[i]==0) distn[i]++;
//cout << distn[i] << "\n";
}
int dist1n[2*n];
for(int i=0;i<2*n;i++){
dist1n[i]=dist1[i]+distn[i]-1;
//cout << dist1n[i] << "?\n";
}
{
priority_queue<pii,vector<pii>,greater<pii>> pq;
for(int i=n;i<2*n;i++){
pq.push(mp(dist1n[i],i));
}
while(!pq.empty()){
auto [w,u]=pq.top();
pq.pop();
if(w!=dist1n[u]) continue;
for(auto [v,w1]:edges[u]){
if(dist1n[v]>w+w1){
dist1n[v]=w+w1;
pq.push(mp(dist1n[v],v));
}
}
}
}
int q;
cin >> q;
while(q--){
int i;
cin >> i;
i--;
if(dist1n[i+n]>=INF-1){
cout << -1 << "\n";
} else cout << dist1n[i+n] << "\n";
}
}
signed main(){
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int t;
//cin >> t;
t=1;
while(t--) solve();
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
}
# | 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... |