#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 3e5 + 10;
const int MOD = 998244353;
#define ll __int128
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
ll read() { int x; cin >> x; return (ll)x; }
long long bm(long long b, long long p) {
if(p==0) return 1 % MOD;
long long r = bm(b, p >> 1);
if(p&1) return (((r*r) % MOD) * b) % MOD;
return (r*r) % MOD;
}
long long inv(long long b) {
return bm(b, MOD-2);
}
long long f[MAXN];
long long nCr(int n, int r) {
long long ans = f[n]; ans *= inv(f[r]); ans %= MOD;
ans *= inv(f[n-r]); ans %= MOD; return ans;
}
long long fib[MAXN], lucas[MAXN];
void precomp() {
for(int i=0; i<MAXN; i++) f[i] = (i == 0 ? 1 % MOD : (f[i-1] * i) % MOD);
lucas[0] = 2;
lucas[1] = 1;
for(int i=2; i<MAXN; i++) lucas[i] = (lucas[i-2] + lucas[i-1]) % MOD;
fib[0] = 0;
fib[1] = 1;
for(int i=2; i<MAXN; i++) fib[i] = (fib[i-2] + fib[i-1]) % MOD;
}
int fastlog(int x) {
return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void google(int i) { cout << "Case #" << i << ": "; }
int csb(int l, int r, int k) { // count number of [l, r] such that i & 2^k > 0
if(l > r) return 0;
if(l == 0) {
int s = r / (1ll << (k+1)); // number of complete cycles
int t = r % (1ll << (k+1));
int ans = s * (1ll << k);
ans += (t >= (1ll << k) ? t - (1ll << k) + 1 : 0);
return ans;
}
else return csb(0, r, k) - csb(0, l - 1, k);
}
int lis(vector<int> a) {
int n = a.size();
int bucket[n+1];
for(int i=1; i<=n; i++) bucket[i] = 1e18;
int ans = 1;
for(int x: a) {
auto it = lower_bound(bucket + 1, bucket +n +1, x);
int d = distance(bucket, it);
ans = max(ans, d);
bucket[d] = min(bucket[d], x);
}
return ans;
}
pair<int, int> str[4*MAXN];
void u(int l, int r, int tar, int idx, int val, int val2) {
if(l == r) {
str[idx] = {val, val2}; return;
}
int mid = (l + r) >> 1;
if(tar <= mid) u(l, mid, tar, 2 * idx + 1, val, val2);
else u(mid + 1, r, tar, 2 * idx + 2, val, val2);
str[idx] = min(str[2*idx+1], str[2*idx+2]);
}
pair<int, int> qu(int l, int r, int constl, int constr, int idx) {
if(l <= constl && constr <= r) return str[idx];
int mid = (constl + constr) >> 1;
if(mid < l || r < constl) return qu(l, r, mid+1, constr, 2*idx+2);
else if(constr < l || r < mid+1) return qu(l, r, constl, mid, 2*idx+1);
else {
return min(qu(l, r, constl, mid, 2*idx+1), qu(l, r, mid+1, constr, 2*idx+2));
}
}
void update(int i, int v, int w) {
u(0, MAXN - 1, i, 0, v, w);
}
int min_idx(int l, int r) {
pair<int, int> res = qu(l, r, 0, MAXN - 1, 0);
if(res.first == 1e16) return -1;
return res.second;
}
void solve(int tc) {
int n, q;
cin >> n >> q;
int s[n+1], e[n+1];
for(int i=1; i<=n; i++) cin >> s[i] >> e[i];
set<int> sett;
unordered_map<int, int> is;
int nxt = 0;
for(int i=1; i<=n; i++) {
sett.insert(s[i]);
sett.insert(e[i]);
}
for(int x: sett) {
nxt++;
is[x] = nxt;
}
for(int i=1; i<=n; i++) s[i] = is[s[i]], e[i] = is[e[i]];
int m = nxt;
pair<int, int> ohno1[m+1];
for(int i=1; i<=m; i++) ohno1[i] = {1e16, 0};
for(int i=1; i<=n; i++) ohno1[e[i]] = min(ohno1[e[i]], {s[i], i});
for(int i=1; i<=m; i++) update(i, ohno1[i].first, ohno1[i].second);
int st[17][n+1];
for(int i=1; i<=n; i++) {
st[0][i] = min_idx(s[i], e[i]);
if(s[st[0][i]] == s[i]) st[0][i] = -1;
// cout << st[0][i] << " \n"[i == n];
}
for(int i=1; i<17; i++) {
for(int j=1; j<=n; j++) {
if(st[i-1][j] != -1) st[i][j] = st[i-1][st[i-1][j]];
else st[i][j] = -1;
}
}
while(q--) {
int x, y;
cin >> x >> y;
int ans = 0;
if(e[x] > e[y]) {
cout << "impossible\n"; continue;
}
if(x == y) {
cout << "0\n"; continue;
}
if(s[y] <= e[x] && e[x] <= e[y]) {
cout << "1\n"; continue;
}
for(int i=16; i>=0; i--) {
int id = st[i][y];
if(id == -1) continue;
if(s[id] > e[x]) {
y = id;
ans += (1 << i);
}
}
//cout << x << " " << y << " " << ans << "\n";
if(x == y) {
cout << ans << "\n"; continue;
}
if(s[y] <= e[x] && e[x] <= e[y]) {
cout << ans + 1 << "\n"; continue;
}
bool done = 0;
for(int i=0; i<3; i++) {
y = st[0][y];
ans++;
if(y == -1) {
break;
}
if(s[y] <= e[x] && e[x] <= e[y]) {
cout << ans + 1 << "\n";
done = 1;
break;
}
}
if(!done) cout << "impossible\n";
}
}
int32_t main() {
precomp();
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; //cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
// I don't know geometry.
// Teaming is unfair.
/*
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
7380 KB |
Output is correct |
2 |
Correct |
140 ms |
40160 KB |
Output is correct |
3 |
Correct |
165 ms |
42252 KB |
Output is correct |
4 |
Correct |
222 ms |
42176 KB |
Output is correct |
5 |
Correct |
185 ms |
43668 KB |
Output is correct |
6 |
Correct |
200 ms |
45196 KB |
Output is correct |
7 |
Correct |
198 ms |
45524 KB |
Output is correct |
8 |
Correct |
257 ms |
58932 KB |
Output is correct |
9 |
Correct |
220 ms |
58944 KB |
Output is correct |
10 |
Correct |
192 ms |
42624 KB |
Output is correct |
11 |
Correct |
253 ms |
48448 KB |
Output is correct |
12 |
Correct |
118 ms |
41900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
7428 KB |
Output is correct |
2 |
Correct |
7 ms |
7380 KB |
Output is correct |
3 |
Correct |
8 ms |
7636 KB |
Output is correct |
4 |
Correct |
8 ms |
7636 KB |
Output is correct |
5 |
Correct |
9 ms |
7636 KB |
Output is correct |
6 |
Correct |
9 ms |
7636 KB |
Output is correct |
7 |
Correct |
9 ms |
7888 KB |
Output is correct |
8 |
Correct |
9 ms |
7892 KB |
Output is correct |
9 |
Correct |
9 ms |
7500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
7428 KB |
Output is correct |
2 |
Correct |
7 ms |
7380 KB |
Output is correct |
3 |
Correct |
8 ms |
7636 KB |
Output is correct |
4 |
Correct |
8 ms |
7636 KB |
Output is correct |
5 |
Correct |
9 ms |
7636 KB |
Output is correct |
6 |
Correct |
9 ms |
7636 KB |
Output is correct |
7 |
Correct |
9 ms |
7888 KB |
Output is correct |
8 |
Correct |
9 ms |
7892 KB |
Output is correct |
9 |
Correct |
9 ms |
7500 KB |
Output is correct |
10 |
Correct |
7 ms |
7428 KB |
Output is correct |
11 |
Correct |
7 ms |
7380 KB |
Output is correct |
12 |
Correct |
8 ms |
7724 KB |
Output is correct |
13 |
Correct |
8 ms |
7636 KB |
Output is correct |
14 |
Correct |
8 ms |
7636 KB |
Output is correct |
15 |
Correct |
8 ms |
7668 KB |
Output is correct |
16 |
Correct |
9 ms |
7780 KB |
Output is correct |
17 |
Correct |
9 ms |
7876 KB |
Output is correct |
18 |
Correct |
8 ms |
7508 KB |
Output is correct |
19 |
Correct |
40 ms |
10472 KB |
Output is correct |
20 |
Correct |
38 ms |
10392 KB |
Output is correct |
21 |
Correct |
40 ms |
10664 KB |
Output is correct |
22 |
Correct |
32 ms |
10676 KB |
Output is correct |
23 |
Correct |
34 ms |
11364 KB |
Output is correct |
24 |
Correct |
31 ms |
11376 KB |
Output is correct |
25 |
Correct |
42 ms |
11004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
7428 KB |
Output is correct |
2 |
Correct |
7 ms |
7380 KB |
Output is correct |
3 |
Correct |
8 ms |
7636 KB |
Output is correct |
4 |
Correct |
8 ms |
7636 KB |
Output is correct |
5 |
Correct |
9 ms |
7636 KB |
Output is correct |
6 |
Correct |
9 ms |
7636 KB |
Output is correct |
7 |
Correct |
9 ms |
7888 KB |
Output is correct |
8 |
Correct |
9 ms |
7892 KB |
Output is correct |
9 |
Correct |
9 ms |
7500 KB |
Output is correct |
10 |
Correct |
7 ms |
7380 KB |
Output is correct |
11 |
Correct |
7 ms |
7380 KB |
Output is correct |
12 |
Correct |
8 ms |
7636 KB |
Output is correct |
13 |
Correct |
10 ms |
7636 KB |
Output is correct |
14 |
Correct |
8 ms |
7636 KB |
Output is correct |
15 |
Correct |
9 ms |
7672 KB |
Output is correct |
16 |
Correct |
9 ms |
7892 KB |
Output is correct |
17 |
Correct |
9 ms |
7892 KB |
Output is correct |
18 |
Correct |
8 ms |
7448 KB |
Output is correct |
19 |
Correct |
123 ms |
38464 KB |
Output is correct |
20 |
Correct |
127 ms |
39592 KB |
Output is correct |
21 |
Correct |
134 ms |
40312 KB |
Output is correct |
22 |
Correct |
149 ms |
45888 KB |
Output is correct |
23 |
Correct |
270 ms |
56688 KB |
Output is correct |
24 |
Correct |
230 ms |
56580 KB |
Output is correct |
25 |
Correct |
42 ms |
23516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
168 ms |
39044 KB |
Output is correct |
2 |
Correct |
162 ms |
42176 KB |
Output is correct |
3 |
Correct |
234 ms |
41992 KB |
Output is correct |
4 |
Correct |
221 ms |
58584 KB |
Output is correct |
5 |
Correct |
203 ms |
42380 KB |
Output is correct |
6 |
Correct |
283 ms |
58524 KB |
Output is correct |
7 |
Correct |
327 ms |
58408 KB |
Output is correct |
8 |
Correct |
287 ms |
58724 KB |
Output is correct |
9 |
Correct |
277 ms |
56564 KB |
Output is correct |
10 |
Correct |
267 ms |
58084 KB |
Output is correct |
11 |
Correct |
292 ms |
57912 KB |
Output is correct |
12 |
Correct |
278 ms |
58248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
7380 KB |
Output is correct |
2 |
Correct |
140 ms |
40160 KB |
Output is correct |
3 |
Correct |
165 ms |
42252 KB |
Output is correct |
4 |
Correct |
222 ms |
42176 KB |
Output is correct |
5 |
Correct |
185 ms |
43668 KB |
Output is correct |
6 |
Correct |
200 ms |
45196 KB |
Output is correct |
7 |
Correct |
198 ms |
45524 KB |
Output is correct |
8 |
Correct |
257 ms |
58932 KB |
Output is correct |
9 |
Correct |
220 ms |
58944 KB |
Output is correct |
10 |
Correct |
192 ms |
42624 KB |
Output is correct |
11 |
Correct |
253 ms |
48448 KB |
Output is correct |
12 |
Correct |
118 ms |
41900 KB |
Output is correct |
13 |
Correct |
7 ms |
7428 KB |
Output is correct |
14 |
Correct |
7 ms |
7380 KB |
Output is correct |
15 |
Correct |
8 ms |
7636 KB |
Output is correct |
16 |
Correct |
8 ms |
7636 KB |
Output is correct |
17 |
Correct |
9 ms |
7636 KB |
Output is correct |
18 |
Correct |
9 ms |
7636 KB |
Output is correct |
19 |
Correct |
9 ms |
7888 KB |
Output is correct |
20 |
Correct |
9 ms |
7892 KB |
Output is correct |
21 |
Correct |
9 ms |
7500 KB |
Output is correct |
22 |
Correct |
7 ms |
7428 KB |
Output is correct |
23 |
Correct |
7 ms |
7380 KB |
Output is correct |
24 |
Correct |
8 ms |
7724 KB |
Output is correct |
25 |
Correct |
8 ms |
7636 KB |
Output is correct |
26 |
Correct |
8 ms |
7636 KB |
Output is correct |
27 |
Correct |
8 ms |
7668 KB |
Output is correct |
28 |
Correct |
9 ms |
7780 KB |
Output is correct |
29 |
Correct |
9 ms |
7876 KB |
Output is correct |
30 |
Correct |
8 ms |
7508 KB |
Output is correct |
31 |
Correct |
40 ms |
10472 KB |
Output is correct |
32 |
Correct |
38 ms |
10392 KB |
Output is correct |
33 |
Correct |
40 ms |
10664 KB |
Output is correct |
34 |
Correct |
32 ms |
10676 KB |
Output is correct |
35 |
Correct |
34 ms |
11364 KB |
Output is correct |
36 |
Correct |
31 ms |
11376 KB |
Output is correct |
37 |
Correct |
42 ms |
11004 KB |
Output is correct |
38 |
Correct |
7 ms |
7380 KB |
Output is correct |
39 |
Correct |
7 ms |
7380 KB |
Output is correct |
40 |
Correct |
8 ms |
7636 KB |
Output is correct |
41 |
Correct |
10 ms |
7636 KB |
Output is correct |
42 |
Correct |
8 ms |
7636 KB |
Output is correct |
43 |
Correct |
9 ms |
7672 KB |
Output is correct |
44 |
Correct |
9 ms |
7892 KB |
Output is correct |
45 |
Correct |
9 ms |
7892 KB |
Output is correct |
46 |
Correct |
8 ms |
7448 KB |
Output is correct |
47 |
Correct |
123 ms |
38464 KB |
Output is correct |
48 |
Correct |
127 ms |
39592 KB |
Output is correct |
49 |
Correct |
134 ms |
40312 KB |
Output is correct |
50 |
Correct |
149 ms |
45888 KB |
Output is correct |
51 |
Correct |
270 ms |
56688 KB |
Output is correct |
52 |
Correct |
230 ms |
56580 KB |
Output is correct |
53 |
Correct |
42 ms |
23516 KB |
Output is correct |
54 |
Correct |
168 ms |
39044 KB |
Output is correct |
55 |
Correct |
162 ms |
42176 KB |
Output is correct |
56 |
Correct |
234 ms |
41992 KB |
Output is correct |
57 |
Correct |
221 ms |
58584 KB |
Output is correct |
58 |
Correct |
203 ms |
42380 KB |
Output is correct |
59 |
Correct |
283 ms |
58524 KB |
Output is correct |
60 |
Correct |
327 ms |
58408 KB |
Output is correct |
61 |
Correct |
287 ms |
58724 KB |
Output is correct |
62 |
Correct |
277 ms |
56564 KB |
Output is correct |
63 |
Correct |
267 ms |
58084 KB |
Output is correct |
64 |
Correct |
292 ms |
57912 KB |
Output is correct |
65 |
Correct |
278 ms |
58248 KB |
Output is correct |
66 |
Correct |
8 ms |
7324 KB |
Output is correct |
67 |
Correct |
140 ms |
42168 KB |
Output is correct |
68 |
Correct |
168 ms |
42160 KB |
Output is correct |
69 |
Correct |
232 ms |
42200 KB |
Output is correct |
70 |
Correct |
177 ms |
43712 KB |
Output is correct |
71 |
Correct |
178 ms |
45132 KB |
Output is correct |
72 |
Correct |
186 ms |
45488 KB |
Output is correct |
73 |
Correct |
212 ms |
58868 KB |
Output is correct |
74 |
Correct |
225 ms |
58984 KB |
Output is correct |
75 |
Correct |
182 ms |
42464 KB |
Output is correct |
76 |
Correct |
208 ms |
48444 KB |
Output is correct |
77 |
Correct |
114 ms |
41836 KB |
Output is correct |
78 |
Correct |
8 ms |
7376 KB |
Output is correct |
79 |
Correct |
8 ms |
7712 KB |
Output is correct |
80 |
Correct |
8 ms |
7648 KB |
Output is correct |
81 |
Correct |
8 ms |
7636 KB |
Output is correct |
82 |
Correct |
8 ms |
7636 KB |
Output is correct |
83 |
Correct |
9 ms |
7880 KB |
Output is correct |
84 |
Correct |
9 ms |
7872 KB |
Output is correct |
85 |
Correct |
10 ms |
7512 KB |
Output is correct |
86 |
Correct |
39 ms |
10664 KB |
Output is correct |
87 |
Correct |
42 ms |
10412 KB |
Output is correct |
88 |
Correct |
41 ms |
10748 KB |
Output is correct |
89 |
Correct |
33 ms |
10700 KB |
Output is correct |
90 |
Correct |
33 ms |
11392 KB |
Output is correct |
91 |
Correct |
32 ms |
11340 KB |
Output is correct |
92 |
Correct |
40 ms |
10992 KB |
Output is correct |
93 |
Correct |
112 ms |
40384 KB |
Output is correct |
94 |
Correct |
105 ms |
39620 KB |
Output is correct |
95 |
Correct |
133 ms |
40296 KB |
Output is correct |
96 |
Correct |
167 ms |
45880 KB |
Output is correct |
97 |
Correct |
255 ms |
56688 KB |
Output is correct |
98 |
Correct |
231 ms |
56684 KB |
Output is correct |
99 |
Correct |
38 ms |
23496 KB |
Output is correct |
100 |
Correct |
310 ms |
58576 KB |
Output is correct |
101 |
Correct |
317 ms |
58576 KB |
Output is correct |
102 |
Correct |
268 ms |
58728 KB |
Output is correct |
103 |
Correct |
289 ms |
58204 KB |
Output is correct |
104 |
Correct |
299 ms |
58032 KB |
Output is correct |
105 |
Correct |
274 ms |
58324 KB |
Output is correct |
106 |
Correct |
163 ms |
37216 KB |
Output is correct |
107 |
Correct |
201 ms |
41780 KB |
Output is correct |
108 |
Correct |
173 ms |
42348 KB |
Output is correct |
109 |
Correct |
181 ms |
42340 KB |
Output is correct |
110 |
Correct |
267 ms |
58468 KB |
Output is correct |
111 |
Correct |
278 ms |
58436 KB |
Output is correct |