#include <bits/stdc++.h>
using namespace std;
#define int long long
//#define hello cout<<"line "<<__LINE__<<endl;
#define hello 69
using ii = pair<int,int>;
vector<ii> adj[400005];
void bfs(int s, int dist[]) {
dist[s] = 0;
priority_queue<ii,vector<ii>,greater<ii>> pq;
for(pq.push({0,s});pq.size();) {
auto [d,x] = pq.top(); pq.pop();
if(d!=dist[x]) continue;
for(auto [i,di]: adj[x]) if(dist[i]>d+di) {
dist[i] = d+di;
pq.push({d+di,i});
}
}
}
main() {
int n; cin >> n;
int l[n], r[n]; for(int i=0;i<n;i++) {cin>>l[i]>>r[i]; l[i]--;}
for(int i=1;i<n;i++) {adj[i<<1].push_back({i,0}); adj[i<<1|1].push_back({i,0});}
for(int i=0;i<n;i++) {
for(int ll=l[i]+n,rr=r[i]+n;ll<rr;ll>>=1,rr>>=1) {
if(ll&1) adj[ll++].push_back({i+n,1});
if(rr&1) adj[--rr].push_back({i+n,1});
}
}
int dista[2*n], distb[2*n], distt[2*n+5];
fill(dista,dista+2*n,12102010);
fill(distb,distb+2*n,12102010);
fill(distt,distt+2*n+5,12102010);
bfs(n,dista);
bfs(2*n-1,distb);
for(int i=0;i<n;i++) adj[2*n].push_back({i+n,dista[i+n]+distb[i+n]});
bfs(2*n,distt);
int q; cin >> q; for(int x;q--;) {
cin >> x;
cout << (distt[x]==12102010?-1:distt[x]+1) << "\n";
}
}
Compilation message
passport.cpp:20:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
20 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
9816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
9816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
