#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0);
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 2e5 + 5;
const int INF = 1e9 + 7;
int l[maxn], r[maxn], ans[maxn];
int d0[maxn], d1[maxn];
vector<pll> adj[maxn * 4];
int idx[maxn];
int n;
void build(int v = 1, int l = 0, int r = n - 1){
if(l == r){
idx[l] = v;
return;
}
int m = (l + r) / 2;
adj[v * 2].eb(v, 0);
adj[v * 2 + 1].eb(v, 0);
build(v * 2, l, m);
build(v * 2 + 1, m + 1, r);
}
void add(int id, int l, int r, int v = 1, int L = 0, int R = n - 1){
if(l > R || r < L) return;
if(l <= L && r >= R){
if(idx[id] != v) adj[v].eb(idx[id], 1);
return;
}
int m = (L + R) / 2;
add(id, l, r, v * 2, L, m);
add(id, l, r, v * 2 + 1, m + 1, R);
}
vector<int> dijkstra(int st){
vector<int> dist(n * 4, INF);
dist[st] = 0;
priority_queue<pll, vector<pll>, greater<pll>> q;
q.push({0, st});
while(!q.empty()){
auto [d, pos] = q.top(); q.pop();
if(dist[pos] != d) continue;
for(auto [x, w] : adj[pos]){
if(dist[x] > dist[pos] + w){
dist[x] = dist[pos] + w;
q.push({dist[x], x});
}
}
}
return dist;
}
signed main(void){
fastio;
cin>>n;
build();
for(int i = 0; i < n; i++){
cin>>l[i]>>r[i];
l[i] --, r[i] --;
add(i, l[i], r[i]);
}
auto dist = dijkstra(idx[0]), d1 = dijkstra(idx[n - 1]);
for(int i = 0; i < n * 4; i++){
dist[i] += d1[i] - 1;
dist[i] = max(dist[i], 0LL);
}
priority_queue<pll, vector<pll>, greater<pll>> q;
for(int i = 0; i < n; i++) q.push({dist[idx[i]], idx[i]});
while(!q.empty()){
auto [d, pos] = q.top(); q.pop();
if(dist[pos] != d) continue;
for(auto [x, w] : adj[pos]){
if(dist[x] > dist[pos] + w){
dist[x] = dist[pos] + w;
q.push({dist[x], x});
}
}
}
int Q;
cin>>Q;
for(int i = 0; i < Q; i++){
int x;
cin>>x;
x = idx[x - 1];
cout<<(dist[x] <= n ? dist[x] : -1)<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
22872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
22876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
22876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
22876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
22872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
