#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, q, L[200005], R[200005], cl[200005], cr[200005];
struct node{
int s, e, m, val;
node *l, *r;
node(int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1;
val = 0;
if(s != e)l = new node(s, m), r = new node(m+1, e);
}
void upd(int p, int v){
if(s == e){
val = v;
return;
}
if(p <= m)l->upd(p, v);
else r->upd(p, v);
val = min(l->val, r->val);
}
int qry(int a, int b){
if(s == a && b == e)return val;
else if(b <= m)return l->qry(a, b);
else if(a > m)return r->qry(a, b);
else return min(l->qry(a, m), r->qry(m+1, b));
}
}*root;
vector <pi> adj[600005];
int dist[600005];
int cnt;
struct node2{
int s, e, m, nd;
node2 *l, *r;
node2(int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1;
nd = ++cnt;
if(s != e){
l = new node2(s, m);
r = new node2(m+1, e);
adj[l->nd].push_back({nd, 0});
adj[r->nd].push_back({nd, 0});
}
else adj[s].push_back({nd, 0});
}
void upd(int a, int b, int u){
if(s == a && e == b){
adj[nd].push_back({u, 1});
return;
}
if(b <= m)l->upd(a, b, u);
else if(a > m)r->upd(a, b, u);
else l->upd(a, m, u), r->upd(m+1, b, u);
}
}*root2;
void solve(){
cin >> n;
for(int i=1;i<=n;i++)cin >> L[i] >> R[i];
root = new node(1, n);
cl[1] = 1, cr[n] = 1;
for(int i=2;i<=n;i++){
if(L[i] == i){
cl[i] = 1e18;
}
else cl[i] = root->qry(L[i], i - 1) + 1;
root->upd(i, cl[i]);
}
root = new node(1, n);
for(int i=n-1;i>=1;i--){
if(R[i] == i){
cr[i] = 1e18;
}
else cr[i] = root->qry(i + 1, R[i]) + 1;
root->upd(i, cr[i]);
}
cnt = n;
root2 = new node2(1, n);
for(int i=1;i<=n;i++)root2->upd(L[i], R[i], i);
priority_queue <pi, vector <pi>, greater <pi> > pq;
for(int i=1;i<=n;i++){
dist[i] = cl[i] + cr[i];
//cout << dist[i] << ' ';
if(L[i] == 1 && R[i] == n)dist[i] = 1;
pq.push({dist[i], i});
}
for(int i=n+1;i<=cnt;i++)dist[i] = 1e18;
while(!pq.empty()){
int x = pq.top().fi, y = pq.top().se;
pq.pop();
if(dist[y] < x)continue;
for(auto [i, j] : adj[y]){
if(dist[i] > x + j)dist[i] = x + j, pq.push({dist[i], i});
}
}
//for(int i=1;i<=cnt;i++)cout << dist[i] << ' ';
//cout << '\n';
cin >> q;
while(q--){
int x; cin >> x;
if(dist[x] > 1e9)cout << -1 << '\n';
else cout << dist[x] << '\n';
}
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int tc = 1;
//cin >> tc;
for(int tc1=1;tc1<=tc;tc1++){
// cout << "Case #" << tc1 << ": ";
solve();
}
}
Compilation message
passport.cpp:122:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
122 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
