#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
const int MAXN = 2e5 + 25;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
const int bad = 1e9;
struct SegmentTree {
int tree[2 * MAXN];
void init () {
for (auto &i : tree) i = bad;
}
void update (int l, int r, int a, int b, int node) {
if (l > a || r < a) return;
if (l == r) {
tree[node] = min(tree[node], b);
return;
}
update(l, mid, a, b, tl);
update(mid + 1, r, a, b, tr);
tree[node] = min(tree[tl], tree[tr]);
}
int get (int l, int r, int a, int b, int node) {
if (l > b || r < a) return bad;
if (l >= a && r <= b) return tree[node];
return min(get(l, mid, a, b, tl), get(mid + 1, r, a, b, tr));
}
} cur;
vector <int> adj[MAXN];
vector <int> arr[MAXN];
vector <int> d;
int dp[MAXN];
vector <vector <int>> events;
int idxx[MAXN];
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
int l, r;
cin >> l >> r;
arr[i] = {l, r, i};
d.push_back(l); d.push_back(r);
}
sort(d.begin(), d.end()); d.resize(unique(d.begin(), d.end()) - d.begin());
for (int i = 1; i <= n; i++) {
arr[i][0] = lower_bound(d.begin(), d.end(), arr[i][0]) - d.begin();
arr[i][1] = lower_bound(d.begin(), d.end(), arr[i][1]) - d.begin();
arr[i][0]++; arr[i][1]++;
}
sort(arr + 1, arr + n + 1, [] (vector <int> &a, vector <int> &b) {
return a[1] == b[1] ? a[0] < b[0] : a[1] < b[1];
});
for (int i = 1; i <= n; i++) idxx[arr[i][2]] = i;
while (q--) {
int a, b;
cin >> a >> b;
if (a == b) {
cout << "0\n";
continue;
}
cur.init();
int ans = -1;
for (int i = idxx[a]; i <= idxx[b]; i++) {
int l = arr[i][0], r = arr[i][1], idx = arr[i][2];
if (idx == a) {
cur.update(1, MAXN, r, 0, 1);
continue;
}
if (idx == b) {
ans = cur.get(1, MAXN, l, r, 1);
break;
}
int x = cur.get(1, MAXN, l, r, 1);
cur.update(1, MAXN, r, x + 1, 1);
}
ans++;
if (ans > n) {
cout << "impossible\n";
} else {
cout << ans << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Execution timed out |
1584 ms |
16676 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1554 ms |
16840 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Execution timed out |
1584 ms |
16676 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
