#include <bits/stdc++.h>
using namespace std;
struct seg {
int L;
int R;
bool operator < (seg s) {
if(R == s.R) return L < s.L;
return R < s.R;
}
};
const int N = 1e5 + 10, LOG = 18;
int n, q;
map<int, int> m;
seg a[N];
int sparse[N][LOG];
int st[8 * N];
int L[2 * 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 1e9;
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++) {
v.push_back({{a[i].L, false}, i});
v.push_back({{a[i].R, true}, i});
}
sort(v.begin(), v.end());
int mx = 0;
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 < 2 * 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, 2 * 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, 2 * n, a[e].L, a[e].R);
if(have <= a[s].R) cout << res + 2 << "\n";
else cout << "impossible\n";
}
return 0;
}
/*
OBS: uvek cu uzimati segment sa najdaljim endom (osim u poslednjem koraku mozda)
0. (mozda kompresija)
1. Za svaki segment nadjem onaj sa najdaljim endom u koji moze da udje (stavim sve u jedan vector, dodajem ih, svaki put kad dodjem do
do enda, nadjem najveci aktivni end)
2. Izbuildujem sparse tabelu nad tim
3. Query: vidim koliko koraka mi treba da dodjem do <=end
-ako sam >=start, ispisem, kraj
-u suprotnom, gledam da li postoji segment sa startom <=gde sam, i endom u zavrsnom intervalu (segmentno nad endovima, rmq), kraj
*/
/*
5 1
1 2
2 3
3 5
4 5
5 6
1 5
*/
Compilation message
events.cpp: In function 'int main()':
events.cpp:66: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]
66 | for(int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 2 |
Incorrect |
188 ms |
20348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
206 ms |
20372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 2 |
Incorrect |
188 ms |
20348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
