oj.uz

Submission #980185

# Submission time Handle Problem Language Result Execution time Memory
980185 2024-05-12T00:43:59 Z asdfgrace Event Hopping (BOI22_events) C++17
50 / 100
 1093 ms 100504 KB 
#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]);
  });
  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 {
    /*
    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';
      }
    }
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 56 ms 14744 KB Output is correct
3 Correct 59 ms 14752 KB Output is correct
4 Correct 64 ms 14740 KB Output is correct
5 Correct 65 ms 14928 KB Output is correct
6 Correct 64 ms 14672 KB Output is correct
7 Correct 60 ms 14672 KB Output is correct
8 Correct 54 ms 15184 KB Output is correct
9 Correct 54 ms 15424 KB Output is correct
10 Correct 81 ms 14996 KB Output is correct
11 Correct 77 ms 15184 KB Output is correct
12 Correct 45 ms 15188 KB Output is correct

Subtask #2
10.0 / 10.0

# 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 10 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #3
15.0 / 15.0

# 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 10 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 9 ms 348 KB Output is correct
13 Correct 1 ms 344 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 1 ms 348 KB Output is correct
19 Correct 612 ms 98980 KB Output is correct
20 Correct 965 ms 100436 KB Output is correct
21 Correct 972 ms 100372 KB Output is correct
22 Correct 798 ms 100504 KB Output is correct
23 Correct 555 ms 100252 KB Output is correct
24 Correct 311 ms 100244 KB Output is correct
25 Correct 950 ms 99820 KB Output is correct

Subtask #4
15.0 / 15.0

# 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 10 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 8 ms 348 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 1 ms 344 KB Output is correct
19 Correct 1093 ms 3980 KB Output is correct
20 Correct 231 ms 4108 KB Output is correct
21 Correct 39 ms 3936 KB Output is correct
22 Correct 99 ms 3920 KB Output is correct
23 Correct 30 ms 3924 KB Output is correct
24 Correct 34 ms 3932 KB Output is correct
25 Correct 22 ms 3932 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 14672 KB Output is correct
2 Correct 58 ms 14672 KB Output is correct
3 Correct 62 ms 14668 KB Output is correct
4 Correct 52 ms 15184 KB Output is correct
5 Correct 80 ms 14908 KB Output is correct
6 Incorrect 113 ms 14996 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 56 ms 14744 KB Output is correct
3 Correct 59 ms 14752 KB Output is correct
4 Correct 64 ms 14740 KB Output is correct
5 Correct 65 ms 14928 KB Output is correct
6 Correct 64 ms 14672 KB Output is correct
7 Correct 60 ms 14672 KB Output is correct
8 Correct 54 ms 15184 KB Output is correct
9 Correct 54 ms 15424 KB Output is correct
10 Correct 81 ms 14996 KB Output is correct
11 Correct 77 ms 15184 KB Output is correct
12 Correct 45 ms 15188 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 10 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 9 ms 348 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 2 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 612 ms 98980 KB Output is correct
32 Correct 965 ms 100436 KB Output is correct
33 Correct 972 ms 100372 KB Output is correct
34 Correct 798 ms 100504 KB Output is correct
35 Correct 555 ms 100252 KB Output is correct
36 Correct 311 ms 100244 KB Output is correct
37 Correct 950 ms 99820 KB Output is correct
38 Correct 0 ms 344 KB Output is correct
39 Correct 0 ms 344 KB Output is correct
40 Correct 8 ms 348 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 2 ms 348 KB Output is correct
43 Correct 1 ms 348 KB Output is correct
44 Correct 1 ms 348 KB Output is correct
45 Correct 1 ms 348 KB Output is correct
46 Correct 1 ms 344 KB Output is correct
47 Correct 1093 ms 3980 KB Output is correct
48 Correct 231 ms 4108 KB Output is correct
49 Correct 39 ms 3936 KB Output is correct
50 Correct 99 ms 3920 KB Output is correct
51 Correct 30 ms 3924 KB Output is correct
52 Correct 34 ms 3932 KB Output is correct
53 Correct 22 ms 3932 KB Output is correct
54 Correct 56 ms 14672 KB Output is correct
55 Correct 58 ms 14672 KB Output is correct
56 Correct 62 ms 14668 KB Output is correct
57 Correct 52 ms 15184 KB Output is correct
58 Correct 80 ms 14908 KB Output is correct
59 Incorrect 113 ms 14996 KB Output isn't correct
60 Halted 0 ms 0 KB -