//≽^•⩊•^≼
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q; cin >> n >> q;
vector<array<int, 2>> v(n);
vector<vector<int>> g(n);
vector<vector<array<int, 2>>> qu(n);
vector<array<int, 20>> gh(n);
vector<int> id(n), root, ans(q, -1), vis(n);
for(auto &[i, l]: v) cin >> i >> l;
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int i, int j){
return (v[i][1]==v[j][1])?v[i][0]<v[j][0]:v[i][1]<v[j][1];
});
vector<int> el;
for(int i=n-1; i>=0; i--){
if(el.size()){
int s=-1;
int gh = el.size()-1;
for(int j=17; j>=0; j--){
int tmp = (s+(1<<j));
if(tmp >= el.size()) continue;
if(v[el[gh-tmp]][0]>v[id[i]][1]) s = tmp;
}
s++;
if(s<el.size() && v[el[gh-s]][0]<=v[id[i]][1]){
g[el[gh-s]].push_back(id[i]);
}
else{
root.push_back(id[i]);
}
}
else root.push_back(id[i]);
while(el.size() && v[el.back()][0]>=v[id[i]][0]){
el.pop_back();
}
el.push_back(id[i]);
}
el.clear();
for(int i=0; i<20; i++){
for(int l=0; l<n; l++){
gh[l][i]=l;
}
}
for(int i=n-1; i>=0; i--){
/* for(auto i: el) cout<<v[i][0]<<" "<<v[i][1]<<"\n";
cout<<"\n";*/
if(el.size()){
int s=-1;
for(int j=17; j>=0; j--){
int tmp = (s+(1<<j));
if(tmp >= el.size()) continue;
// if(tmp==
if(v[el[tmp]][0]>v[id[i]][1]) s=tmp;
}
s++;
if(s<el.size() && v[el[s]][0]<=v[id[i]][1]){
gh[id[i]][0]=el[s];
}
}
if(el.size() && v[el.back()][0]>=v[id[i]][0]){
el.push_back(id[i]);
}
else el.push_back(id[i]);
}
el.clear();
int cnt = 0;
while(q--){
int x, y; cin >> x >> y;
x--; y--;
if(x==y) ans[cnt++]=0;
else
qu[x].push_back({y, cnt++});
}
vector<int> s;
int count=0;
vector<int> par(n);
auto c = [&](int x, int y){
if(v[x][1]==v[y][1]){
return v[x][0]<v[y][0];
}
return v[x][1]<v[y][1];
};
for(int i=1; i<20; i++){
for(int l=0; l<n; l++){
gh[l][i] = gh[gh[l][i-1]][i-1];
}
}
auto func =[&](int x, int y){
int h=0;
for(int j=19; j>=0; j--){
if(c(gh[x][j], y)&&(j==0||gh[x][j]!=gh[x][j-1])){
h+=(1<<j); x=gh[x][j];
}
}
return h+1;
};
auto dfs =[&](int vv, int p, auto&&dfs)->void{
vis[vv] = 1;
// cout<<vv<<" "<<count<<"\n";
for(auto [j, i]: qu[vv]){
if(!vis[j]) continue;
ans[i] = func(vv, j);
}
for(auto i: g[vv]){
dfs(i, vv, dfs);
}
vis[vv] = 0;
};
for(auto i: root) count=1, dfs(i,i, dfs);
// cout<<val[4671];
for(auto j: ans){
if(j!=-1) cout<<j<<endl;
else cout<<"impossible\n";
//else cout<<j-1<<"\n";
}
}
Compilation message
events.cpp: In function 'int main()':
events.cpp:37:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | if(tmp >= el.size()) continue;
| ~~~~^~~~~~~~~~~~
events.cpp:43:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | if(s<el.size() && v[el[gh-s]][0]<=v[id[i]][1]){
| ~^~~~~~~~~~
events.cpp:78:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | if(tmp >= el.size()) continue;
| ~~~~^~~~~~~~~~~~
events.cpp:84:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | if(s<el.size() && v[el[s]][0]<=v[id[i]][1]){
| ~^~~~~~~~~~
events.cpp:108:9: warning: variable 'count' set but not used [-Wunused-but-set-variable]
108 | int count=0;
| ^~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
212 ms |
44076 KB |
Output is correct |
| 3 |
Correct |
202 ms |
44572 KB |
Output is correct |
| 4 |
Correct |
261 ms |
44780 KB |
Output is correct |
| 5 |
Incorrect |
185 ms |
42948 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
860 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
860 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
860 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
860 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
860 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
860 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
228 ms |
43924 KB |
Output is correct |
| 2 |
Correct |
203 ms |
44696 KB |
Output is correct |
| 3 |
Correct |
244 ms |
44964 KB |
Output is correct |
| 4 |
Correct |
70 ms |
30252 KB |
Output is correct |
| 5 |
Correct |
151 ms |
39200 KB |
Output is correct |
| 6 |
Correct |
196 ms |
45204 KB |
Output is correct |
| 7 |
Correct |
181 ms |
45076 KB |
Output is correct |
| 8 |
Correct |
138 ms |
42200 KB |
Output is correct |
| 9 |
Correct |
72 ms |
41148 KB |
Output is correct |
| 10 |
Correct |
201 ms |
44512 KB |
Output is correct |
| 11 |
Correct |
204 ms |
44212 KB |
Output is correct |
| 12 |
Correct |
203 ms |
44512 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
212 ms |
44076 KB |
Output is correct |
| 3 |
Correct |
202 ms |
44572 KB |
Output is correct |
| 4 |
Correct |
261 ms |
44780 KB |
Output is correct |
| 5 |
Incorrect |
185 ms |
42948 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
