#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
const int maxn = 2e5+10;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;
int n, q;
pair<int, int> s[maxn];
vector< int > v;
int dp[30][maxn];
int mini[maxn];
int tour[logo][treesiz];
void update(int ind, int x, int val) {
x += off;
tour[ind][x] = val;
x /= 2;
while (x) tour[ind][x] = min(tour[ind][x * 2], tour[ind][x * 2 + 1]), x /= 2;
}
int query(int ind, int a, int b, int l, int r, int node) {
if (l > b || r < a) return inf;
if (l >= a && r <= b) return tour[ind][node];
int mid = (l + r) / 2;
return min(query(ind, a, b, l, mid, node * 2), query(ind, a, b, mid + 1, r, node * 2 + 1));
}
int main() {
scanf("%d%d", &n, &q);
for (int i = 0; i < n; i++) {
int a, b;
scanf("%d%d", &a, &b);
s[i] = {a, b};
v.push_back(a);
v.push_back(b);
}
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
for (int i = 0; i < v.size(); i++) mini[i] = i;
for (int i = 0; i < n; i++) {
s[i].X = lower_bound(v.begin(), v.end(), s[i].X) - v.begin();
s[i].Y = lower_bound(v.begin(), v.end(), s[i].Y) - v.begin();
mini[s[i].Y] = min(mini[s[i].Y], s[i].X);
}
for (int i = 0; i < v.size(); i++) {
dp[0][i] = mini[i];
//printf("mini %d --> %d\n", i, mini[i]);
}
for (int i = 1; i < logo; i++) {
for (int j = 0; j < v.size(); j++) update(i - 1, j, dp[i - 1][j]);
for (int j = 0; j < v.size(); j++) {
dp[i][j] = query(i - 1, dp[i - 1][j], j, 0, off - 1, 1);
}
}
for (int i = 0; i < v.size(); i++) update(logo - 1, i, dp[logo - 1][i]);
while (q--) {
int a, b;
scanf("%d%d", &a, &b); a--, b--;
if (s[a].Y > s[b].Y) {
printf("impossible\n");
continue;
}
if (a == b) {
printf("0\n");
continue;
}
int ca = a, cb = b;
int sol = inf;
int dis = 0;
b = s[b].Y;
a = s[a].Y;
for (int i = logo - 1; i >= 0; i--) {
if (dp[i][b] > a) b = dp[i][b], dis += (1 << i);
//printf("debug: %d %d\n", a, b);
}
if (mini[b] <= a)
sol = min(sol, dis + 2);
else {
printf("impossible\n");
continue;
}
dis = 0;
b = s[cb].Y;
int l = s[cb].X;
for (int i = logo - 1; i >= 0; i--) {
int tren = query(i, l, b, 0, off - 1, 1);
if (tren > a) l = tren, dis += (1 << i);
//printf("debug: %d %d %d\n", a, l, b);
}
if (query(0, l, b, 0, off - 1, 1) <= a) sol = min(dis + 2, sol);
if (sol >= inf) printf("impossible\n");
else printf("%d\n", sol);
}
return 0;
}
Compilation message
events.cpp: In function 'int main()':
events.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int i = 0; i < v.size(); i++) mini[i] = i;
| ~~^~~~~~~~~~
events.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
events.cpp:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int j = 0; j < v.size(); j++) update(i - 1, j, dp[i - 1][j]);
| ~~^~~~~~~~~~
events.cpp:61:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for (int j = 0; j < v.size(); j++) {
| ~~^~~~~~~~~~
events.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for (int i = 0; i < v.size(); i++) update(logo - 1, i, dp[logo - 1][i]);
| ~~^~~~~~~~~~
events.cpp:78:7: warning: unused variable 'ca' [-Wunused-variable]
78 | int ca = a, cb = b;
| ^~
events.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | scanf("%d%d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~
events.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | scanf("%d%d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~
events.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | scanf("%d%d", &a, &b); a--, b--;
| ~~~~~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1620 KB |
Output is correct |
| 2 |
Correct |
1201 ms |
27680 KB |
Output is correct |
| 3 |
Correct |
1130 ms |
27664 KB |
Output is correct |
| 4 |
Incorrect |
1180 ms |
27956 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1620 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1620 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1696 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
1748 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1620 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1620 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1696 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
1748 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1620 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1620 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1696 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
1748 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1184 ms |
27752 KB |
Output is correct |
| 2 |
Correct |
1165 ms |
27768 KB |
Output is correct |
| 3 |
Incorrect |
1168 ms |
27596 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1620 KB |
Output is correct |
| 2 |
Correct |
1201 ms |
27680 KB |
Output is correct |
| 3 |
Correct |
1130 ms |
27664 KB |
Output is correct |
| 4 |
Incorrect |
1180 ms |
27956 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
