#include <bits/stdc++.h>
using namespace std;
#define ar array
#define fi first
#define se second
#define sz(x) (int)x.size()
#define rep(i, b, e) for (int i = (b); i <= (e); i++)
#define rrep(i, b, e) for (int i = (b); i >= (e); i--)
typedef long long ll;
typedef pair<ll, ll> ii;
template <class T>
bool minimize(T &a, const T &b) {
if(a > b) {a = b; return 1;}
return 0;
}
template <class T>
bool maximize(T &a, const T &b) {
if(a < b) {a = b; return 1;}
return 0;
}
const int N = 5e3 + 7;
int n, q, s[N], e[N];
void read() {
cin >> n >> q;
rep(i, 1, n) cin >> s[i] >> e[i];
}
int d[N][N];
vector<int> adj[N];
void sub3() {
rep(i, 1, n) rep(j, 1, n) {
if (s[j] <= e[i] && e[i] <= e[j]) {
adj[i].push_back(j);
}
}
memset(d, -1, sizeof d);
rep(i, 1, n) {
queue<int> q;
q.push(i); d[i][i] = 0;
while (sz(q)) {
int u = q.front(); q.pop();
for (int v: adj[u]) if (d[i][v] == -1) {
d[i][v] = d[i][u] + 1;
q.push(v);
}
}
}
while (q--) {
int l, r;
cin >> l >> r;
(d[l][r] == -1 ? cout << "impossible\n" : cout << d[l][r] << '\n');
}
}
int mn[N];
map<int, int> pos;
int jump(int cur, int st, int des) {
int l = st, r = des, ans = -1;
while (l <= r) {
int mid = l + r >> 1;
if (mn[mid] > cur) r = mid - 1;
else l = mid + 1, ans = mid;
}
return ans;
}
void sub4() {
vector<ii> vec;
rep(i, 1, n) vec.push_back({e[i], i});
sort(vec.begin(), vec.end(), [&](ii x, ii y){
return (x.fi == y.fi ? s[x.se] < s[y.se] : x.fi < y.fi);
});
rep(i, 0, n - 1) pos[vec[i].fi] = i;
mn[n - 1] = s[vec.back().se];
rrep(i, n - 2, 0) mn[i] = min(mn[i + 1], s[vec[i].se]);
for (int u, v; q; q--){
cin >> u >> v;
int l = pos[e[u]], r = pos[e[v]], ans = 0, ok = 1;
int cur = e[u];
while (cur < s[v]) {
int nxt = jump(cur, l, r);
// cerr << cur << ' ' << nxt << endl;
if (nxt == -1) {
ok = 0;
break;
}
ans++; cur = vec[nxt].fi;
}
if (u > v || !ok) cout << "Impossible\n";
else cout << ans << '\n';
}
}
void solve() {
if (q <= 100) sub4();
else if (n <= 5000) sub3();
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
if (fopen("test.inp", "r")) {
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
read();
solve();
}
/**
+ check mod (gõ đúng số), limit, kiểu dữ liệu
+ check format output
+mấy bài multitest:
quên reset biến, mảng, (nên dùng fill, memset, v.v)
quên xuống dòng
precompute đầu bài
+nhập hết dữ liệu trước khi return
+xóa debug
**/
Compilation message
events.cpp: In function 'int jump(int, int, int)':
events.cpp:69:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
69 | int mid = l + r >> 1;
| ~~^~~
events.cpp: In function 'int main()':
events.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
113 | freopen("test.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | freopen("test.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1573 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
724 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1573 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
