#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
const ll N = 6e5 + 100;
const ll inf = 1e17;
const ll mod = 1e9 + 7;
const ll block = 350;
vector<ll>adj[5 * N], rev[5 * N];
ll d[5 * N][2];
ll dp[5 * N];
ll n,q;
struct cmp{
bool operator()(const pll &a, const pll &b){
return a.S > b.S;
}
};
void dijk(ll s, ll typ){
priority_queue<pll, vector<pll>, cmp>q;
for(int i = 1; i <= 9 * n;i++) d[i][typ] = inf;
d[s][typ] = 0;
q.push({s, d[s][typ]});
while(q.size()){
ll u = q.top().F, c = q.top().S; q.pop();
if(c != d[u][typ]) continue;
for(auto v : rev[u]){
if(d[u][typ] + (v >= 8 * n + 1) < d[v][typ]){
d[v][typ] = d[u][typ] + (v >= 8 * n + 1);
q.push({v, d[v][typ]});
}
}
}
}
void finalize(){
priority_queue<pll, vector<pll>, cmp>q;
for(int i = 1; i <= 9 * n;i++) dp[i] = d[i][0] + d[i][1] - (i >= 8 * n + 1), q.push({i, dp[i]});
while(q.size()){
ll u = q.top().F, c = q.top().S; q.pop();
if(c != dp[u]) continue;
for(auto v : rev[u]){
if(dp[u] + (v >= 8 * n + 1) < dp[v]){
dp[v] = dp[u] + (v >= 8 * n + 1);
q.push({v, dp[v]});
}
}
}
}
void build1(ll id, ll l, ll r){
if(l == r){
adj[id].pb(8 * n + l);
adj[8 * n + l].pb(id);
rev[id].pb(8 * n + l);
rev[8 * n + l].pb(id);
return;
}
ll mid = (l + r) / 2;
build1(2 * id, l, mid); build1(2 * id + 1, mid + 1, r);
adj[id].pb(2 * id); adj[id].pb(2 * id + 1);
rev[2 * id].pb(id); rev[2 * id + 1].pb(id);
}
void build2(ll id, ll l, ll r){
if(l == r) {
adj[4 * n + id].pb(8 * n + l);
adj[8 * n + l].pb(4 * n + id);
rev[8 * n + l].pb(4 * n + id);
rev[4 * n + id].pb(8 * n + l);
return;
}
ll mid = (l + r) / 2;
build2(2 * id, l, mid); build2(2 * id + 1, mid + 1, r);
adj[4 * n + 2 * id].pb(4 * n + id);
rev[4 * n + id].pb(4 * n + 2 * id);
adj[4 * n + 2 * id + 1].pb(4 * n + id);
rev[4 * n + id].pb(4 * n + 2 * id + 1);
}
void add_edge2(ll id, ll l, ll r, ll left, ll right, ll v){
if(l > right || r < left) return;
if(left <= l && r <= right){
adj[8 * n + v].pb(id);
rev[id].pb(8 * n + v);
return;
}
ll mid = (l + r) / 2;
add_edge2(2 * id, l, mid, left, right, v);
add_edge2(2 * id + 1, mid + 1, r, left, right, v);
}
void to_thic_cau(){
cin >> n;
build1(1,1,n); build2(1,1,n);
for(int i = 1; i <= n;i++){
ll l,r; cin >> l >> r;
add_edge2(1,1,n,l,r,i);
}
dijk(8 * n + 1, 0); dijk(9 * n, 1); finalize();
cin >> q;
while(q--){
ll x; cin >> x;
cout << (dp[8 * n + x] >= inf ? -1 : dp[8 * n + x]) << "\n";
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ll tc = 1;
//cin >> tc;
while(tc--) to_thic_cau();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
141140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
141136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
141136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
141136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
141140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
