#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7;
const int mxn = 5e5, mxm = 1e5, sq = 400;
const int base = (1 << 18);
const ll inf = 1e9;
const ld pre = 1e-6;
//cool problem!
int n;
int l[mxn + 1], r[mxn + 1], id, lson[2 * mxn + 5], rson[2 * mxn + 5];
vt<pii>adj[2 * mxn + 5];
vt<ll>d1, d2, d3;
int build(int nd, int l, int r){
if(l == r)return(l);
int mid = (l + r) >> 1;
int ls = build(nd << 1, l, mid), rs = build(nd << 1 | 1, mid + 1, r);
++id;
lson[id] = ls; rson[id] = rs;
adj[lson[id]].emplace_back(id, 0); adj[rson[id]].emplace_back(id, 0);
return(id);
}
void upd(int nd, int l, int r, int ql, int qr, int u){
if(ql > r || qr < l)return;
if(ql <= l && qr >= r){
adj[nd].emplace_back(u, 1);
return;
}
int mid = (l + r) >> 1;
upd(lson[nd], l, mid, ql, qr, u); upd(rson[nd], mid + 1, r, ql, qr, u);
}
void find(vt<ll>&d){
deque<int>dq;
for(int i = 1; i <= n; i++){
if(d[i] >= inf)dq.pb(i);
}
while(!dq.empty()){
int u = dq.front(); dq.pop_front();
for(auto [v, w]: adj[u]){
if(d[v] > d[u] + w){
d[v] = d[u] + w;
if(w){
dq.pb(v);
}else{
dq.push_front(v);
}
}
}
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
id = n;
int root = build(1, 1, n);
forr(i, 1, n + 1){
cin >> l[i] >> r[i];
upd(root, 1, n, l[i], r[i], i);
}
d1.resize(2 * n + 5, inf); d1[1] = 0;
find(d1);
d1[1] = 1;
d2.resize(2 * n + 5, inf); d2[n] = 0;
find(d2);
d2[n] = 1;
int q; cin >> q;
d3.resize(4 * n + 1, inf);
for(int i = 1; i <= n; i++){
d3[i] = min(d1[i] + d2[i], inf);
}
find(d3);
forr(i, 0, q){
int x; cin >> x;
if(d3[x] >= 1e9)cout << -1 << "\n";
else cout << d3[x] - 1 << "\n";
}
return(0);
}
Compilation message
passport.cpp: In function 'void find(std::vector<long long int>&)':
passport.cpp:58:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
58 | for(auto [v, w]: adj[u]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
