#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100001;
const int K = 20;
struct Node {
Node *left, *right;
int best = 0, start = INT_MAX, tl, tr;
Node(int l_, int r_) : tl(l_), tr(r_) {}
void expand() {
if (left == nullptr) {
int tm = (tl + tr) / 2;
left = new Node(tl, tm);
right = new Node(tm+1, tr);
}
}
void upd(int l, int r, int val) {
if (l > r) return;
if (l == tl && r == tr) {
best = max(best, val);
} else {
expand();
int m = (tl + tr) / 2;
left->upd(l, min(r, m), val);
right->upd(max(l, m+1), r, val);
}
}
void upd2(int l, int r, int val) {
if (l > r) return;
if (l == tl && r == tr) {
start = min(start, val);
} else {
expand();
int m = (tl + tr) / 2;
left->upd2(l, min(r, m), val);
right->upd2(max(l, m+1), r, val);
}
}
int qry(int pos) {
if (tl == tr) {
return best;
} else {
expand();
int m = (tl + tr) / 2;
if (pos <= m) {
return max(best, left->qry(pos));
} else {
return max(best, right->qry(pos));
}
}
}
int qry2(int pos) {
if (tl == tr) {
return start;
} else {
expand();
int m = (tl + tr) / 2;
if (pos <= m) {
return min(start, left->qry2(pos));
} else {
return min(start, right->qry2(pos));
}
}
}
};
int up[MAXN][K];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, q; cin >> n >> q;
Node *root = new Node(1, 2e9);
vector<pair<int, int>> events(n+1);
map<int, int> m;
for (int i = 1; i <= n; i++) {
cin >> events[i].first >> events[i].second;
if (m.count(events[i].second)) {
if (events[m[events[i].second]].first > events[i].first) {
m[events[i].second] = i;
}
} else {
m[events[i].second] = i;
}
root->upd(events[i].first, events[i].second, events[i].second);
root->upd2(events[i].first, events[i].second, events[i].first);
}
for (int i = 1; i <= n; i++) {
up[i][0] = m[root->qry(events[i].second)];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j < K; j++) {
up[i][j] = up[up[i][j-1]][j-1];
}
}
while (q--) {
int a, b; cin >> a >> b;
int ans = 0;
if (a == b) {
cout << "0\n";
continue;
}
if (events[a].second > events[b].second) {
cout << "impossible\n";
continue;
}
for (int it = 0; it < 30 && a != b; it++) {
int best = -1, cur = 0;
for (int i = 0; i < K && up[a][i]; i++) {
if (events[up[a][i]].second <= events[b].first && up[a][i] != a && (i == 0 || up[a][i] != up[a][i-1])) {
best = up[a][i];
cur = 1 << i;
}
}
if (best != -1) {
a = best;
ans += cur;
}
if (a == b) break;
}
if (a == b) {
cout << "0\n";
} else if (events[a].second == events[b].first || events[b].first < events[a].second) {
cout << ans+1 << "\n";
} else if (root->qry2(events[b].first) <= events[a].second) {
cout << ans+2 << "\n";
} else {
cout << "impossible\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
610 ms |
132460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
