#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define ld long double
#define el cout << '\n'
#define f1(i,n) for(ll i=1;i<=n;i++)
#define __file_name ""
using namespace std;
const ll maxn = 1e6+5, inf=1e18;
ll n, rpos[maxn], l, r, lf[maxn], rt[maxn], q, x, d[maxn], d1[maxn],dn[maxn];
vector<pair<ll,ll>> G[maxn];
bool vis[maxn];
priority_queue<pll, vector<pll>, greater<pll>> pq;
void addEdge(ll u, ll v, ll w){
// cout << u << " -> " << v << " w = " << w;el;
G[u].push_back({v, w});
}
void build(ll idx, ll l, ll r){
if(l == r){
rpos[l] = idx;
return;
}
// addEdge(idx, idx*2, 0);
// addEdge(idx, idx*2+1, 0);
addEdge(idx*2, idx, 0);
addEdge(idx*2+1, idx, 0);
ll mid = (l+r)/2;
build(idx*2, l, mid);
build(idx*2+1, mid+1, r);
}
void addSeg(ll idx, ll l, ll r, ll u, ll v, ll tar, ll w){
// connects tar -> [u,v] if not rev
if(r < u || v < l) return;
if(u <= l && r <= v){
addEdge(idx, tar, w);
return;
}
ll mid = (l+r)/2;
addSeg(idx*2, l, mid, u, v, tar, w);
addSeg(idx*2+1, mid+1, r, u, v, tar, w);
}
void calc(){
while(!pq.empty()){
pair<ll,ll> item = pq.top();
pq.pop();
ll dist = item.first, u = item.second;
if(dist != d[u]) continue;
vis[u] = true;
for(pair<ll,ll> e: G[u]){
ll c = e.first, w = e.second;
if(d[u] + w < d[c]){
// cout << u << " -> " << c << " changed: " << d[u] + w;el;
d[c] = d[u] + w;
pq.push({d[c], c});
}
}
}
}
void dijkstra(ll s){
d[0] = inf;
f1(i,4*n) d[i] = inf;
d[s] = 0ll;
pq.push({d[s], s});
calc();
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
if(fopen(__file_name ".inp", "r")){
freopen(__file_name ".inp","r",stdin);
freopen(__file_name ".out","w",stdout);
}
// code here
cin >> n;
build(1, 1, n);
f1(i,n){
cin >> l >> r;
lf[i] = l; rt[i] = r;
if(l != i){
addSeg(1,1,n,l,i-1,rpos[i],1);
}
if(i != r){
addSeg(1,1,n,i+1,r,rpos[i],1);
}
}
dijkstra(rpos[1]);
f1(i,n) d1[i] = d[rpos[i]];
dijkstra(rpos[n]);
f1(i,n) dn[i] = d[rpos[i]];
f1(i,4*n) d[i] = inf;
f1(i,n) {
// cout << i << " = " << d1[i] << ' ' << dn[i];el;
d[rpos[i]] = d1[i] + dn[i] - (lf[i] == 1 && rt[i] == n);
pq.push({d[rpos[i]], rpos[i]});
}
calc();
cin >> q;
while(q--){
cin >> x;
// cout << x << " = " << rpos[x];el;
cout << (d[rpos[x]] < inf ? d[rpos[x]] : -1);el;
}
return 0;
}
Compilation message
passport.cpp: In function 'int main()':
passport.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | freopen(__file_name ".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | freopen(__file_name ".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23900 KB |
Output is correct |
| 2 |
Correct |
11 ms |
23956 KB |
Output is correct |
| 3 |
Incorrect |
11 ms |
23900 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
23896 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
23900 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
23896 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
23900 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
23896 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
23900 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23900 KB |
Output is correct |
| 2 |
Correct |
11 ms |
23956 KB |
Output is correct |
| 3 |
Incorrect |
11 ms |
23900 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
