#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int par[20][200005], n, q, S[200005], E[200005];
pi A[200005], B[200005];
struct node{
int s, e, m, val = 1e10;
node *l, *r;
node(int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1;
if(s != e)l = new node(s, m), r = new node(m+1, e);
}
void upd(int p, int v){
if(s == e)val = min(val, v);
else{
if(p <= m)l->upd(p, v);
else r->upd(p, v);
val = min(l->val, r->val);
}
}
int qry(int a, int b){
if(a == s && b == e)return val;
else if(b <= m)return l->qry(a, b);
else if(a > m)return r->qry(a, b);
else return min(l->qry(a, m), r->qry(m+1, b));
}
}*root;
map <int, int> mp;
vector <int> lol;
void solve(){
cin >> n >> q;
root = new node(1, 2 * n);
for(int i=1;i<=n;i++){
cin >> S[i] >> E[i];
A[i] = {S[i], i};
B[i] = {E[i], i};
lol.push_back(S[i]);
lol.push_back(E[i]);
}
sort(lol.begin(), lol.end());
int cnt = 0, prv = -1e10;
for(auto i : lol){
if(i == prv)continue;
prv = i;
mp[i] = ++cnt;
}
for(int i=1;i<=n;i++)root->upd(mp[E[i]], S[i]);
sort(A+1, A+n+1);
sort(B+1, B+n+1);
int in = 1, mx = 0, idx = -1;
for(int i=1;i<=n;i++){
while(in <= n && A[in].fi <= B[i].fi){
if(mx < E[A[in].se])mx = E[A[in].se], idx = A[in].se;
in++;
}
if(mx > B[i].fi)par[0][B[i].se] = idx;
}
for(int i=1;i<=19;i++)for(int j=1;j<=n;j++)par[i][j] = par[i-1][par[i-1][j]];
while(q--){
int s, e; cin >> s >> e;
if(E[s] > E[e])cout << "impossible\n";
else if(s == e)cout << 0 << '\n';
else if(S[e] <= E[s] && E[s] <= E[e])cout << 1 << '\n';
else{
int ans = 0, cur = s;
for(int i=19;i>=0;i--){
int x = par[i][cur];
if(x == 0)continue;
if(E[x] < S[e])cur = par[i][cur], ans += (1 << i);
}
if(par[0][cur] == 0){
cout << "impossible\n";
continue;
}
ans+=2;
if(root->qry(mp[S[e]], mp[E[e]]) <= E[cur])cout << ans << '\n';
else {
ans++;
int brub = n + 1, lo = 1, hi = n;
while (lo <= hi){
int mid = (lo + hi) >> 1;
if(B[mid].fi >= S[e])brub = mid, hi = mid - 1;
else lo = mid + 1;
}
brub--;
if(brub == 0)cout << "impossible\n";
else{
if(root->qry(mp[S[e]], mp[E[e]]) <= B[brub].fi)cout << ans << '\n';
else cout << "impossible\n";
}
}
}
}
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int tc = 1;
//cin >> tc;
for(int tc1=1;tc1<=tc;tc1++){
// cout << "Case #" << tc1 << ": ";
solve();
}
}
Compilation message
events.cpp:110:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
110 | main(){
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
468 KB |
Output is correct |
2 |
Correct |
195 ms |
54188 KB |
Output is correct |
3 |
Correct |
209 ms |
54288 KB |
Output is correct |
4 |
Correct |
299 ms |
54184 KB |
Output is correct |
5 |
Correct |
240 ms |
54924 KB |
Output is correct |
6 |
Correct |
237 ms |
55540 KB |
Output is correct |
7 |
Correct |
232 ms |
55756 KB |
Output is correct |
8 |
Correct |
285 ms |
60932 KB |
Output is correct |
9 |
Correct |
261 ms |
60232 KB |
Output is correct |
10 |
Correct |
230 ms |
54608 KB |
Output is correct |
11 |
Correct |
276 ms |
57092 KB |
Output is correct |
12 |
Correct |
92 ms |
53936 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
1024 KB |
Output is correct |
5 |
Incorrect |
2 ms |
980 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
1024 KB |
Output is correct |
5 |
Incorrect |
2 ms |
980 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
1024 KB |
Output is correct |
5 |
Incorrect |
2 ms |
980 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
222 ms |
54168 KB |
Output is correct |
2 |
Correct |
236 ms |
54176 KB |
Output is correct |
3 |
Correct |
319 ms |
54220 KB |
Output is correct |
4 |
Correct |
256 ms |
60192 KB |
Output is correct |
5 |
Correct |
291 ms |
54596 KB |
Output is correct |
6 |
Correct |
401 ms |
60612 KB |
Output is correct |
7 |
Correct |
400 ms |
60668 KB |
Output is correct |
8 |
Correct |
347 ms |
60756 KB |
Output is correct |
9 |
Correct |
179 ms |
59944 KB |
Output is correct |
10 |
Correct |
309 ms |
60280 KB |
Output is correct |
11 |
Correct |
265 ms |
60072 KB |
Output is correct |
12 |
Correct |
308 ms |
60364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
468 KB |
Output is correct |
2 |
Correct |
195 ms |
54188 KB |
Output is correct |
3 |
Correct |
209 ms |
54288 KB |
Output is correct |
4 |
Correct |
299 ms |
54184 KB |
Output is correct |
5 |
Correct |
240 ms |
54924 KB |
Output is correct |
6 |
Correct |
237 ms |
55540 KB |
Output is correct |
7 |
Correct |
232 ms |
55756 KB |
Output is correct |
8 |
Correct |
285 ms |
60932 KB |
Output is correct |
9 |
Correct |
261 ms |
60232 KB |
Output is correct |
10 |
Correct |
230 ms |
54608 KB |
Output is correct |
11 |
Correct |
276 ms |
57092 KB |
Output is correct |
12 |
Correct |
92 ms |
53936 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
0 ms |
468 KB |
Output is correct |
15 |
Correct |
1 ms |
980 KB |
Output is correct |
16 |
Correct |
1 ms |
1024 KB |
Output is correct |
17 |
Incorrect |
2 ms |
980 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |