#include <bits/stdc++.h>
using namespace std;
#define dbg(x) //x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << " "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));
const int inf = 2e9 + 5;
/*
o(n^2):
for (each event)
add edge from this one to every range that contains it
and basically
you want to find the shortest path from i to j
note - if e[i] = e[j], there will be cycles in the graph
but these aren't that useful unless you want to jump directly from i to j
so we will be dealing with a dag here
so you wouldn't want to switch from anything with the same end
so e[i] must strictly increase
note that if no contained pairs
and you do have a CONTIGIOUS range of indices that you can hop to next
how to solve in n^2?
precomputing answers?
just get all the edges
maybe run n dijkstra? is this different bc dag?
for (cur node)
for (next node)
if (reachable)
for (each node)
dist[node][next] = min(dist[node][next], dist[node][cur] + 1)
or maybe just run a dijkstra if you have all the edges and n <= 1000 and q <= 100
greedy?
if you CANNOT reach the dest from here, you should go to the latest ending event
so that it starts before the dest ends
what about when does it end
if it ends before the dest ends that's fine
it has to end after the dest starts
it cannot end after the dest ends
NOTE: while we must have s[j] <= e[i] we don't have to maximize or minimize it
then we want to pick the maximum possible e[j] <= e[d]
so we can make like a pref max for end values based on start values have to be less
than or equal to whatever
but that won't factor in the "e[j] <= e[d]"
but that's a good reformulation
given max start, what is max e[j] <= e[d]?
we should be able to do queries offline then
so that for each query
we make some new values valid
subtask 3?
for (each end - inc)
upd the end
for (each start - dec)
if start == end
dp[i][d] = 0
if can go from start to end
dp[i][d] = 1
find max s[j] <= e[i], e[j] <= e[d]
dp[i][d] = dp[i][max] + 1
subtask 5?
keep the greedy
still always wanna go to the next event with maximal e[j] <= e[d]
note that s and e are in the same order
so basically
from the start
how many moves can you make while e[j] < s[d]
*/
template <class T> struct SegTree {
int n;
vector<T> st;
T init;
SegTree (int x, T y) {
n = x;
init = y;
st.resize(2 * n, y);
}
void upd(int k, T x) {
k += n;
st[k] = x;
for (k /= 2; k >= 1; k /= 2) {
st[k] = max(st[k * 2], st[k * 2 + 1]);
}
}
T quer(int l, int r) {
l += n; r += n;
T res = init;
while (r >= l && l >= 1) {
if (l % 2 == 1) res = max(res, st[l++]);
if (r % 2 == 0) res = max(res, st[r--]);
l /= 2; r /= 2;
}
return res;
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, q;
cin >> n >> q;
vector<array<int, 3>> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i][0] >> a[i][1];
a[i][2] = i;
}
sort(a.begin(), a.end(), [&] (array<int, 3> x, array<int, 3> y) {
return x[1] < y[1] || (x[1] == y[1] && x[0] < y[0]);
});
bool cont = false;
int mx0 = 0;
for (int i = 0; i < n; i++) {
mx0 = max(mx0, a[i][0]);
if (mx0 != a[i][0]) {
cont = true;
break;
}
}
parr2d(a);
vector<int> at(n);
for (int i = 0; i < n; i++) {
at[a[i][2]] = i;
}
if (q <= 100) {
vector<array<int, 3>> quer(q);
for (int i = 0; i < q; i++) {
cin >> quer[i][0] >> quer[i][1];
quer[i][0]--; quer[i][1]--;
quer[i][0] = at[quer[i][0]];
quer[i][1] = at[quer[i][1]];
quer[i][2] = i;
}
sort(quer.begin(), quer.end(), [&] (array<int, 3> x, array<int, 3> y) {
return x[1] < y[1];
});
parr2d(quer);
vector<int> ans(q, -1);
SegTree<int> pmx(n, 0);
vector<int> s(n);
for (int i = 0; i < n; i++) {
s[i] = a[i][0];
}
sort(s.begin(), s.end());
vector<int> ords(n);
iota(ords.begin(), ords.end(), 0);
sort(ords.begin(), ords.end(), [&] (int x, int y) {
return a[x][0] < a[y][0];
});
vector<int> ats(n);
for (int i = 0 ; i < n; i++) {
ats[ords[i]] = i;
}
int j = 0;
for (int i = 0; i < q; i++) {
if (a[quer[i][0]][1] > a[quer[i][1]][1]) continue;
for (; j < n && a[j][1] <= a[quer[i][1]][1]; j++) {
pmx.upd(ats[j], a[j][1]);
}
if (quer[i][0] == quer[i][1]) {ans[quer[i][2]] = 0; continue;}
int rb = a[quer[i][0]][1], res = 0;
while (rb < a[quer[i][1]][0]) { // if rb < a[quer[i][1]][0], then you can't go to whatever the end is
int k = upper_bound(s.begin(), s.end(), rb) - s.begin() - 1;
int mx = pmx.quer(0, k);
if (mx == rb) {
res = -2;
break;
}
rb = mx;
res++;
}
res++;
ans[quer[i][2]] = res;
}
for (int i = 0; i < q; i++) {
if (ans[i] == -1) {
cout << "impossible\n";
} else {
cout << ans[i] << '\n';
}
}
} else if (n <= 5000) {
/*
subtask 3?
for (each end - inc)
upd the end
for (each start - dec)
if start == end
dp[i][d] = 0
if can go from start to end
dp[i][d] = 1
find max s[j] <= e[i], e[j] <= e[d]
dp[i][d] = dp[i][max] + 1
*/
pv(n);
array<int, 2> init = {0, 0};
SegTree<array<int, 2>> pmx(n, init);
vector<int> s(n);
for (int i = 0; i < n; i++) {
s[i] = a[i][0];
}
sort(s.begin(), s.end());
vector<int> ords(n);
iota(ords.begin(), ords.end(), 0);
sort(ords.begin(), ords.end(), [&] (int x, int y) {
return a[x][0] < a[y][0];
});
vector<int> ats(n);
for (int i = 0 ; i < n; i++) {
ats[ords[i]] = i;
}
vector<int> lb(n);
for (int i = 0; i < n; i++) {
lb[i] = upper_bound(s.begin(), s.end(), a[i][1]) - s.begin() - 1;
}
vector<vector<int>> ans(n, vector<int>(n, -1));
for (int r = 0; r < n; r++) {
pmx.upd(ats[r], {a[r][1], r});
for (int l = n - 1; l >= 0; l--) {
if (a[l][1] > a[r][1]) {
ans[l][r] = -1;
} else if (l == r) {
ans[l][r] = 0;
} else if (a[l][1] >= a[r][0]) {
ans[l][r] = 1;
} else {
pv(l); pv(r);
array<int, 2> best = pmx.quer(0, lb[l]);
parr(best);
if (ans[best[1]][r] == -1) {
ans[l][r] = -1;
} else {
ans[l][r] = ans[best[1]][r] + 1;
}
}
}
}
while (q--) {
int l, r;
cin >> l >> r;
l--; r--;
l = at[l]; r = at[r];
if (ans[l][r] == -1) {
cout << "impossible\n";
} else {
cout << ans[l][r] << '\n';
}
}
} else if (!cont) {
vector<int> to(n), s(n);
for (int i = 0; i < n; i++) {
s[i] = a[i][0];
}
for (int i = 0; i < n; i++) {
to[i] = upper_bound(s.begin(), s.end(), a[i][1]) - s.begin() - 1;
}
vector<vector<int>> lift(n, vector<int>(20, 0));
for (int i = 0; i < 20; i++) {
lift[i][0] = to[i];
}
for (int j = 1; j < 20; j++) {
for (int i = 0; i < n; i++) {
lift[i][j] = lift[lift[i][j - 1]][j - 1];
}
}
while (q--) {
int l, r;
cin >> l >> r;
l--; r--;
l = at[l]; r = at[r];
if (a[l][1] > a[r][1]) {
cout << "impossible\n";
} else if (l == r) {
cout << 0 << '\n';
} else if (a[l][1] == a[r][1]) {
cout << 1 << '\n';
} else {
int ans = 0;
for (int j = 19; j >= 0; j--) {
if (a[lift[l][j]][1] < a[r][0]) {
ans += 1 << j;
l = lift[l][j];
}
}
l = lift[l][0];
ans++;
if (a[l][1] >= a[r][0]) {
cout << ans + 1 << '\n';
} else {
cout << "impossible\n";
}
}
}
} else {
/*
binary lifting probably?
where are you going
the thing on the right with lowest left value, hope it's this
except you can have some annoying 2-cycles or smth
so maybe calc dist to nearest 2cyc
*/
vector<int> to(n, n);
int mnl = inf, ind = n;
for (int i = n - 1; i >= 0; i--) {
if (mnl <= a[i][1]) {
to[i] = ind;
}
if (a[i][0] < mnl) {
mnl = a[i][0];
ind = i;
}
}
vector<bool> cyc(n, false);
for (int i = 1; i < n; i++) {
if (a[i][1] == a[i - 1][1]) {
pv(i);
to[i - 1] = i;
to[i] = i - 1;
cyc[i - 1] = cyc[i] = true;
if (i > 2) assert(a[i - 2][1] != a[i][1]);
}
}
vector<vector<int>> lift(n, vector<int>(20, 0));
for (int i = 0; i < n; i++) {
lift[i][0] = to[i];
}
for (int j = 1; j < 20; j++) {
for (int i = 0; i < n; i++) {
lift[i][j] = (lift[i][j - 1] == n ? n : lift[lift[i][j - 1]][j - 1]);
}
}
parr(to);
while (q--) {
int l, r;
cin >> l >> r;
l--; r--;
l = at[l]; r = at[r];
int ans = 0;
for (int j = 19; j >= 0; j--) {
if (lift[l][j] < n && !cyc[lift[l][j]] && lift[l][j] <= r) {
l = lift[l][j];
ans += (1 << j);
}
}
if (cyc[r]) {
for (int i = 0; i < 2; i++) {
l = to[l];
ans++;
if (l == r) break;
}
}
if (l != r) {
cout << "impossible\n";
} else {
cout << ans << '\n';
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
62 ms |
18708 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
8 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
2 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
344 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
8 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
2 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
344 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
8 ms |
344 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
2 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
632 ms |
100124 KB |
Output is correct |
| 20 |
Correct |
990 ms |
100244 KB |
Output is correct |
| 21 |
Correct |
986 ms |
100436 KB |
Output is correct |
| 22 |
Correct |
806 ms |
100620 KB |
Output is correct |
| 23 |
Correct |
571 ms |
100252 KB |
Output is correct |
| 24 |
Correct |
338 ms |
100360 KB |
Output is correct |
| 25 |
Correct |
967 ms |
99988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
8 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
2 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
344 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
9 ms |
472 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
2 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
344 KB |
Output is correct |
| 18 |
Correct |
1 ms |
344 KB |
Output is correct |
| 19 |
Correct |
1075 ms |
5928 KB |
Output is correct |
| 20 |
Correct |
234 ms |
5132 KB |
Output is correct |
| 21 |
Correct |
40 ms |
5720 KB |
Output is correct |
| 22 |
Correct |
99 ms |
5720 KB |
Output is correct |
| 23 |
Correct |
30 ms |
5724 KB |
Output is correct |
| 24 |
Correct |
35 ms |
5872 KB |
Output is correct |
| 25 |
Correct |
21 ms |
5212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
18768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
62 ms |
18708 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
