oj.uz

답안 #980157

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
980157 2024-05-12T00:23:22 Z asdfgrace Event Hopping (BOI22_events) C++17
35 / 100
 1500 ms 15464 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)
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]
*/

struct SegTree {
  int n;
  vector<int> st;
  
  SegTree (int x) {
    n = x;
    st.resize(2 * n, 0);
  }
  
  void upd(int k, int x) {
    k += n;
    st[k] = x;
    for (k /= 2; k >= 1; k /= 2) {
      st[k] = max(st[k * 2], st[k * 2 + 1]);
    }
  }
  
  int quer(int l, int r) {
    l += n; r += n;
    int res = 0;
    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 || n <= 5000) {
    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 pmx(n);
    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 {
    /*
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 58 ms 14560 KB Output is correct
3 Correct 61 ms 14592 KB Output is correct
4 Correct 65 ms 14672 KB Output is correct
5 Correct 62 ms 14676 KB Output is correct
6 Correct 62 ms 14672 KB Output is correct
7 Correct 63 ms 14616 KB Output is correct
8 Correct 57 ms 15024 KB Output is correct
9 Correct 56 ms 15464 KB Output is correct
10 Correct 77 ms 14948 KB Output is correct
11 Correct 79 ms 14932 KB Output is correct
12 Correct 47 ms 15188 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 7 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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 7 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 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 7 ms 348 KB Output is correct
13 Correct 1 ms 348 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 Execution timed out 1598 ms 2140 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 7 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 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 7 ms 348 KB Output is correct
13 Correct 1 ms 348 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 1020 ms 3976 KB Output is correct
20 Correct 221 ms 3920 KB Output is correct
21 Correct 40 ms 3920 KB Output is correct
22 Correct 97 ms 3920 KB Output is correct
23 Correct 30 ms 3924 KB Output is correct
24 Correct 41 ms 3924 KB Output is correct
25 Correct 21 ms 3928 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 14688 KB Output is correct
2 Correct 61 ms 14676 KB Output is correct
3 Correct 64 ms 14680 KB Output is correct
4 Correct 53 ms 15184 KB Output is correct
5 Correct 78 ms 14940 KB Output is correct
6 Incorrect 104 ms 15328 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 58 ms 14560 KB Output is correct
3 Correct 61 ms 14592 KB Output is correct
4 Correct 65 ms 14672 KB Output is correct
5 Correct 62 ms 14676 KB Output is correct
6 Correct 62 ms 14672 KB Output is correct
7 Correct 63 ms 14616 KB Output is correct
8 Correct 57 ms 15024 KB Output is correct
9 Correct 56 ms 15464 KB Output is correct
10 Correct 77 ms 14948 KB Output is correct
11 Correct 79 ms 14932 KB Output is correct
12 Correct 47 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 7 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 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 7 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 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 Execution timed out 1598 ms 2140 KB Time limit exceeded
32 Halted 0 ms 0 KB -