#include <bits/stdc++.h>
using namespace std ;
const int MAX = 2e5 + 10 ;
int L[MAX] , R[MAX] ;
int n , q ;
void compress()
{
vector<int>v ;
for(int i = 1 ; i <= n ; ++i)
v.push_back(L[i]) , v.push_back(R[i]) ;
sort(v.begin() , v.end()) ;
v.erase(unique(v.begin() , v.end()) , v.end()) ;
for(int i = 1 ; i <= n ; ++i)
{
L[i] = lower_bound(v.begin() , v.end() , L[i]) - v.begin() ;
R[i] = lower_bound(v.begin() , v.end() , R[i]) - v.begin() ;
L[i]++ , R[i]++ ;
}
}
int to[MAX][20] ;
int query(int a , int b)
{
if(a == b)
return 0 ;
int x = R[a] , y = L[b] ;
int ans = 0 ;
for(int i = 19 ; i >= 0 ; --i)
{
if(to[x][i] < y)
x = to[x][i] , ans += (1 << i) ;
}
if(to[x][0] >= y && to[x][0] <= R[b])
return (ans+2) ;
else
return (-1) ;
}
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n>>q ;
for(int i = 1 ; i <= n ; ++i)
cin>>L[i]>>R[i] ;
compress() ;
for(int i = 1 ; i <= n ; ++i)
to[L[i]][0] = R[i] ;
for(int i = 1 ; i <= 2*n ; ++i)
{
to[i][0] = max(to[i][0] , to[i-1][0]) ;
if(to[i][0] < i)
to[i][0] = 2*n+1 ;
}
to[2*n+1][0] = 2*n+1 ;
for(int j = 1 ; j < 20 ; ++j)
{
for(int i = 1 ; i <= 2*n+1 ; ++i)
to[i][j] = to[to[i][j-1]][j-1] ;
}
while(q--)
{
int x , y ;
cin>>x>>y ;
int ans = query(x , y) ;
if(ans != -1)
cout<<ans<<"\n" ;
else
cout<<"impossible\n" ;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
117 ms |
17972 KB |
Output is correct |
3 |
Correct |
121 ms |
18040 KB |
Output is correct |
4 |
Incorrect |
122 ms |
17920 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
124 ms |
17964 KB |
Output is correct |
2 |
Correct |
115 ms |
17952 KB |
Output is correct |
3 |
Incorrect |
132 ms |
17992 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
117 ms |
17972 KB |
Output is correct |
3 |
Correct |
121 ms |
18040 KB |
Output is correct |
4 |
Incorrect |
122 ms |
17920 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |