oj.uz

Submission #980298

# Submission time Handle Problem Language Result Execution time Memory
980298 2024-05-12T03:57:17 Z asdfgrace Event Hopping (BOI22_events) C++17
70 / 100
 1112 ms 100436 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]);
  });
  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) {
    pv(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 < 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[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];
          }
        }
        if (a[l][1] < a[r][0]) {
          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';
      }
    }
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 64 ms 14928 KB Output is correct
3 Correct 66 ms 18000 KB Output is correct
4 Correct 75 ms 18288 KB Output is correct
5 Correct 64 ms 17744 KB Output is correct
6 Correct 63 ms 17744 KB Output is correct
7 Correct 64 ms 17848 KB Output is correct
8 Correct 58 ms 18512 KB Output is correct
9 Correct 66 ms 18508 KB Output is correct
10 Correct 81 ms 18512 KB Output is correct
11 Correct 115 ms 18052 KB Output is correct
12 Correct 55 ms 17744 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 1 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 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 344 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 1 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 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 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 8 ms 496 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 630 ms 98984 KB Output is correct
20 Correct 950 ms 99096 KB Output is correct
21 Correct 960 ms 99424 KB Output is correct
22 Correct 798 ms 99408 KB Output is correct
23 Correct 566 ms 99244 KB Output is correct
24 Correct 334 ms 99156 KB Output is correct
25 Correct 950 ms 98988 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 1 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 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 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 8 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 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 1112 ms 3920 KB Output is correct
20 Correct 233 ms 4176 KB Output is correct
21 Correct 39 ms 4172 KB Output is correct
22 Correct 98 ms 4184 KB Output is correct
23 Correct 30 ms 3932 KB Output is correct
24 Correct 36 ms 3972 KB Output is correct
25 Correct 21 ms 4096 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 14928 KB Output is correct
2 Correct 65 ms 18000 KB Output is correct
3 Correct 73 ms 18004 KB Output is correct
4 Correct 64 ms 18600 KB Output is correct
5 Correct 81 ms 18384 KB Output is correct
6 Correct 89 ms 18180 KB Output is correct
7 Correct 85 ms 18256 KB Output is correct
8 Correct 73 ms 18640 KB Output is correct
9 Correct 30 ms 5712 KB Output is correct
10 Correct 64 ms 17992 KB Output is correct
11 Correct 63 ms 17744 KB Output is correct
12 Correct 64 ms 18008 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 64 ms 14928 KB Output is correct
3 Correct 66 ms 18000 KB Output is correct
4 Correct 75 ms 18288 KB Output is correct
5 Correct 64 ms 17744 KB Output is correct
6 Correct 63 ms 17744 KB Output is correct
7 Correct 64 ms 17848 KB Output is correct
8 Correct 58 ms 18512 KB Output is correct
9 Correct 66 ms 18508 KB Output is correct
10 Correct 81 ms 18512 KB Output is correct
11 Correct 115 ms 18052 KB Output is correct
12 Correct 55 ms 17744 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 8 ms 348 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 344 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 8 ms 496 KB Output is correct
25 Correct 1 ms 348 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 0 ms 348 KB Output is correct
31 Correct 630 ms 98984 KB Output is correct
32 Correct 950 ms 99096 KB Output is correct
33 Correct 960 ms 99424 KB Output is correct
34 Correct 798 ms 99408 KB Output is correct
35 Correct 566 ms 99244 KB Output is correct
36 Correct 334 ms 99156 KB Output is correct
37 Correct 950 ms 98988 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 8 ms 348 KB Output is correct
41 Correct 1 ms 344 KB Output is correct
42 Correct 1 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 348 KB Output is correct
47 Correct 1112 ms 3920 KB Output is correct
48 Correct 233 ms 4176 KB Output is correct
49 Correct 39 ms 4172 KB Output is correct
50 Correct 98 ms 4184 KB Output is correct
51 Correct 30 ms 3932 KB Output is correct
52 Correct 36 ms 3972 KB Output is correct
53 Correct 21 ms 4096 KB Output is correct
54 Correct 64 ms 14928 KB Output is correct
55 Correct 65 ms 18000 KB Output is correct
56 Correct 73 ms 18004 KB Output is correct
57 Correct 64 ms 18600 KB Output is correct
58 Correct 81 ms 18384 KB Output is correct
59 Correct 89 ms 18180 KB Output is correct
60 Correct 85 ms 18256 KB Output is correct
61 Correct 73 ms 18640 KB Output is correct
62 Correct 30 ms 5712 KB Output is correct
63 Correct 64 ms 17992 KB Output is correct
64 Correct 63 ms 17744 KB Output is correct
65 Correct 64 ms 18008 KB Output is correct
66 Correct 0 ms 348 KB Output is correct
67 Correct 67 ms 18104 KB Output is correct
68 Correct 68 ms 18240 KB Output is correct
69 Correct 81 ms 18004 KB Output is correct
70 Correct 64 ms 17844 KB Output is correct
71 Correct 61 ms 17748 KB Output is correct
72 Correct 65 ms 17740 KB Output is correct
73 Correct 55 ms 18312 KB Output is correct
74 Correct 65 ms 18644 KB Output is correct
75 Correct 80 ms 18396 KB Output is correct
76 Correct 79 ms 18116 KB Output is correct
77 Correct 55 ms 17736 KB Output is correct
78 Correct 0 ms 348 KB Output is correct
79 Correct 8 ms 348 KB Output is correct
80 Correct 1 ms 348 KB Output is correct
81 Correct 2 ms 348 KB Output is correct
82 Correct 1 ms 348 KB Output is correct
83 Correct 1 ms 348 KB Output is correct
84 Correct 1 ms 348 KB Output is correct
85 Correct 1 ms 348 KB Output is correct
86 Correct 615 ms 100120 KB Output is correct
87 Correct 948 ms 100252 KB Output is correct
88 Correct 983 ms 100436 KB Output is correct
89 Correct 795 ms 100420 KB Output is correct
90 Correct 581 ms 100180 KB Output is correct
91 Correct 329 ms 100288 KB Output is correct
92 Correct 949 ms 99924 KB Output is correct
93 Correct 1078 ms 5896 KB Output is correct
94 Correct 232 ms 5132 KB Output is correct
95 Correct 40 ms 5808 KB Output is correct
96 Correct 99 ms 5932 KB Output is correct
97 Correct 30 ms 5716 KB Output is correct
98 Correct 35 ms 5716 KB Output is correct
99 Correct 27 ms 5088 KB Output is correct
100 Correct 91 ms 18260 KB Output is correct
101 Correct 85 ms 18256 KB Output is correct
102 Correct 73 ms 18508 KB Output is correct
103 Correct 63 ms 18000 KB Output is correct
104 Correct 66 ms 17772 KB Output is correct
105 Correct 65 ms 17988 KB Output is correct
106 Runtime error 23 ms 5976 KB Execution killed with signal 6
107 Halted 0 ms 0 KB -