#include <bits/stdc++.h>
using namespace std;
struct seg {
int L;
int R;
};
const int N = 1e5 + 10, LOG = 18;
int n, q;
map<int, int> m;
seg a[N];
int sparse[N][LOG];
int st[16 * N];
int L[4 * N];
void build(int index, int l, int r) {
if(l > r) return;
if(l == r) {
st[index] = L[l];
return;
}
int mid = (l + r) / 2;
build(2 * index + 1, l, mid);
build(2 * index + 2, mid + 1, r);
st[index] = min(st[2 * index + 1], st[2 * index + 2]);
}
int get(int index, int l, int r, int L, int R) {
if(l > r || r < L || R < l) return 1000000000;
if(L <= l && r <= R) return st[index];
int mid = (l + r) / 2;
return min(get(2 * index + 1, l, mid, L, R), get(2 * index + 2, mid + 1, r, L, R));
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
vector<int> compress;
for(int i = 0; i < n; i++) {
cin >> a[i].L >> a[i].R;
compress.push_back(a[i].L);
compress.push_back(a[i].R);
}
sort(compress.begin(), compress.end());
for(int i = 0; i < n; i++) {
int oldL = a[i].L, oldR = a[i].R;
a[i].L = lower_bound(compress.begin(), compress.end(), a[i].L) - compress.begin();
a[i].R = lower_bound(compress.begin(), compress.end(), a[i].R) - compress.begin();
m[oldL] = a[i].L;
m[oldR] = a[i].R;
}
vector<pair<pair<int, bool>, int>> v;
for(int i = 0; i < n; i++) {
assert(a[i].L <= 2 * n);
assert(a[i].R <= 2 * n);
v.push_back({{a[i].L, false}, i});
v.push_back({{a[i].R, true}, i});
}
sort(v.begin(), v.end());
int mx = v[0].second;
for(int i = 0; i < v.size(); i++) {
if(v[i].first.second) {
if(a[v[i].second].R == a[mx].R) sparse[v[i].second][0] = -1;
else sparse[v[i].second][0] = mx;
} else {
if(a[mx].R < a[v[i].second].R) mx = v[i].second;
}
}
for(int j = 1; j < LOG; j++) {
for(int i = 0; i < n; i++) {
if(sparse[i][j - 1] == -1) sparse[i][j] = -1;
else sparse[i][j] = sparse[sparse[i][j - 1]][j - 1];
}
}
for(int i = 0; i < 4 * N; i++) L[i] = 1e9;
for(int i = 0; i < n; i++) L[a[i].R] = min(L[a[i].R], a[i].L);
build(0, 0, 4 * n);
while(q--) {
int s, e;
cin >> s >> e;
s--;
e--;
if(s == e) {
cout << "0\n";
continue;
}
if(a[s].R > a[e].R) {
cout << "impossible\n";
continue;
}
if(a[s].R >= a[e].L) {
cout << "1\n";
continue;
}
int res = 0;
for(int j = LOG - 1; j >= 0; j--) {
if(sparse[s][j] == -1) continue;
if(a[sparse[s][j]].R >= a[e].L) continue;
s = sparse[s][j];
res += (1 << j);
}
int have = get(0, 0, 4 * n, a[e].L, a[e].R);
if(have <= a[s].R) cout << res + 2 << "\n";
else cout << "impossible\n";
}
return 0;
}
Compilation message
events.cpp: In function 'int main()':
events.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, bool>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1876 KB |
Output is correct |
2 |
Correct |
203 ms |
23444 KB |
Output is correct |
3 |
Correct |
201 ms |
23476 KB |
Output is correct |
4 |
Correct |
216 ms |
23460 KB |
Output is correct |
5 |
Correct |
207 ms |
24020 KB |
Output is correct |
6 |
Correct |
207 ms |
24504 KB |
Output is correct |
7 |
Correct |
196 ms |
24660 KB |
Output is correct |
8 |
Correct |
196 ms |
28736 KB |
Output is correct |
9 |
Correct |
225 ms |
28684 KB |
Output is correct |
10 |
Correct |
216 ms |
23808 KB |
Output is correct |
11 |
Correct |
236 ms |
25824 KB |
Output is correct |
12 |
Correct |
130 ms |
23968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1860 KB |
Output is correct |
2 |
Correct |
2 ms |
1876 KB |
Output is correct |
3 |
Correct |
3 ms |
2132 KB |
Output is correct |
4 |
Correct |
3 ms |
2132 KB |
Output is correct |
5 |
Incorrect |
4 ms |
2132 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1860 KB |
Output is correct |
2 |
Correct |
2 ms |
1876 KB |
Output is correct |
3 |
Correct |
3 ms |
2132 KB |
Output is correct |
4 |
Correct |
3 ms |
2132 KB |
Output is correct |
5 |
Incorrect |
4 ms |
2132 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1860 KB |
Output is correct |
2 |
Correct |
2 ms |
1876 KB |
Output is correct |
3 |
Correct |
3 ms |
2132 KB |
Output is correct |
4 |
Correct |
3 ms |
2132 KB |
Output is correct |
5 |
Incorrect |
4 ms |
2132 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
203 ms |
23532 KB |
Output is correct |
2 |
Correct |
222 ms |
23544 KB |
Output is correct |
3 |
Correct |
296 ms |
23492 KB |
Output is correct |
4 |
Correct |
199 ms |
28676 KB |
Output is correct |
5 |
Correct |
218 ms |
23788 KB |
Output is correct |
6 |
Correct |
241 ms |
28352 KB |
Output is correct |
7 |
Correct |
271 ms |
28388 KB |
Output is correct |
8 |
Correct |
294 ms |
28492 KB |
Output is correct |
9 |
Correct |
195 ms |
27628 KB |
Output is correct |
10 |
Correct |
269 ms |
27912 KB |
Output is correct |
11 |
Correct |
286 ms |
27836 KB |
Output is correct |
12 |
Correct |
310 ms |
27932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1876 KB |
Output is correct |
2 |
Correct |
203 ms |
23444 KB |
Output is correct |
3 |
Correct |
201 ms |
23476 KB |
Output is correct |
4 |
Correct |
216 ms |
23460 KB |
Output is correct |
5 |
Correct |
207 ms |
24020 KB |
Output is correct |
6 |
Correct |
207 ms |
24504 KB |
Output is correct |
7 |
Correct |
196 ms |
24660 KB |
Output is correct |
8 |
Correct |
196 ms |
28736 KB |
Output is correct |
9 |
Correct |
225 ms |
28684 KB |
Output is correct |
10 |
Correct |
216 ms |
23808 KB |
Output is correct |
11 |
Correct |
236 ms |
25824 KB |
Output is correct |
12 |
Correct |
130 ms |
23968 KB |
Output is correct |
13 |
Correct |
2 ms |
1860 KB |
Output is correct |
14 |
Correct |
2 ms |
1876 KB |
Output is correct |
15 |
Correct |
3 ms |
2132 KB |
Output is correct |
16 |
Correct |
3 ms |
2132 KB |
Output is correct |
17 |
Incorrect |
4 ms |
2132 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |