#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <queue>
#include <cassert>
using namespace std;
const int maxn=1e5+5, Log=17, pot=(1<<Log);
vector < int > svi;
void query(int L, int D, int x, int l, int d){
if(L>=l && D<=d){
svi.push_back(x);
return;
}
if((L+D)/2>=l){
query(L, (L+D)/2, x*2, l, d);
}
if((L+D)/2+1<=d){
query((L+D)/2+1, D, x*2+1, l, d);
}
}
pair < int, int > a[maxn];
set < int > s;
map < int, int > m;
int dist[pot*2];
int d[maxn];
vector < pair < int, int > > ms[pot*2];
void precompute(){
for(int i=2; i<pot*2; i++){
ms[i].push_back({i/2, 0});
}
}
void bfs(int x){
memset(dist, -1, sizeof(dist));
memset(d, -1, sizeof(d));
queue < int > q1, q2;
q1.push(a[x].second+pot);
dist[a[x].second+pot]=0;
d[x]=0;
int tren=0;
while(!q1.empty()){
while(!q1.empty()){
x=q1.front();
q1.pop();
for(int i=0; i<(int)ms[x].size(); i++){
if(ms[x][i].second){
if(dist[ms[x][i].first]==-1){
dist[ms[x][i].first]=tren+1;
q2.push(ms[x][i].first);
}
if(d[ms[x][i].second]==-1){
d[ms[x][i].second]=tren+1;
}
}
else{
if(dist[ms[x][i].first]==-1){
dist[ms[x][i].first]=tren;
q1.push(ms[x][i].first);
}
}
}
}
swap(q1, q2);
tren++;
}
}
int main(){
assert(0);
precompute();
int n, q;
scanf("%d%d", &n, &q);
for(int i=1; i<=n; i++){
scanf("%d%d", &a[i].first, &a[i].second);
s.insert(a[i].first);
s.insert(a[i].second);
}
int br=0;
for(auto it=s.begin(); it!=s.end(); it++){
m[*it]=br;
br++;
}
for(int i=1; i<=n; i++){
a[i]={m[a[i].first], m[a[i].second]};
// cout << a[i].first << ' ' << a[i].second << endl;
query(0, pot-1, 1, a[i].first, a[i].second);
while(!svi.empty()){
// cout << "moji " << svi.back() << endl;
ms[svi.back()].push_back({a[i].second+pot, i});
svi.pop_back();
}
}
int x, y;
for(int i=0; i<q; i++){
scanf("%d%d", &x, &y);
bfs(x);
if(d[y]==-1){
printf("impossible\n");
}
else{
printf("%d\n", d[y]);
}
}
return 0;
}
Compilation message
events.cpp: In function 'int main()':
events.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | scanf("%d%d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~
events.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
85 | scanf("%d%d", &a[i].first, &a[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | scanf("%d%d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
12884 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
12796 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
12796 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
12796 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
12884 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
12884 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
