#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<pair<int,int>,int> a,pair<pair<int,int>,int> b){
return a.first.second<b.first.second;
}
int P[100001][17],ind[100001];
pair<long long,long long> seg[800001];
void build(int p,int l,int r){
if(l==r){
seg[p] = {1e18,-1};
return ;
}
int md = (l+r)/2;
build(p*2,l,md);build(p*2+1,md+1,r);
seg[p] = min(seg[p*2],seg[p*2+1]);
}
pair<long long,long long> query(int p,int l,int r,int lq,int rq){
if(l>=lq&&r<=rq)return seg[p];
if(r<lq||l>rq)return {1e18,-1};
int md = (l+r)/2;
return min(query(p*2,l,md,lq,rq),query(p*2+1,md+1,r,lq,rq));
}
void update(int p,int l,int r,int idx,pair<long long,long long> val){
if(l==r){
seg[p] = min(seg[p],val);
return ;
}
int md = (l+r)/2;
if(idx<=md)update(p*2,l,md,idx,val);
else update(p*2+1,md+1,r,idx,val);
seg[p] = min(seg[p*2],seg[p*2+1]);
}
signed main(){
int n,q;cin>>n>>q;
vector<pair<pair<long long,long long>,int>> v;
map<int,int> comp,sav;
for(int i = 0;i<n;i++){
int a,b;
cin>>a>>b;
comp[a]++;comp[b]++;
v.push_back({{a,b},i});
}
long long z = 0;
for(auto i:comp){
sav[i.first] = ++z;
}
for(int i = 0;i<n;i++){
v[i].first.first = sav[v[i].first.first];
v[i].first.second = sav[v[i].first.second];
}
//sort(v.begin(),v.end());
build(1,0,z);
for(long long i = 0;i<v.size();i++){
update(1,0,z,v[i].first.second,{v[i].first.first,i});
}
int in = 0;
for(int i = 0;i<v.size();i++){
ind[v[i].second] = i;
P[i][0] = query(1,0,z,v[i].first.first,v[i].first.second).second;
//cout<<P[i][0]<<" "<<v[i].first.first<<" "<<v[i].first.second<<endl;
}
for(int i = n-1;i>=0;i--){
for(int j = 1;j<17;j++){
P[i][j] = P[P[i][j-1]][j-1];
}
}
while(q--){
int a,b;cin>>a>>b;
a--;b--;a = ind[a] , b = ind[b];
if(a==b){
cout<<0<<endl;
continue;
}else if(v[b].first.first<=v[a].first.second&&v[a].first.second<=v[b].first.second){
cout<<1<<endl;
continue;
}
int sum = 1 , cur = b;
//cout<<cur<<endl;
for(int i = 16;i>=0;i--){
if(v[P[cur][i]].first.first>v[a].first.second){
sum+=(1<<i);
cur = P[cur][i];
}
}
if(v[P[cur][0]].first.first<=v[a].first.second||v[P[cur][0]].first.second>=v[a].first.second){
cout<<sum+1<<endl;
}else cout<<"impossible\n";
}
}
Compilation message
events.cpp: In function 'int main()':
events.cpp:53:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(long long i = 0;i<v.size();i++){
| ~^~~~~~~~~
events.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for(int i = 0;i<v.size();i++){
| ~^~~~~~~~~
events.cpp:56:9: warning: unused variable 'in' [-Wunused-variable]
56 | int in = 0;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
360 ms |
24228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
