Submission #1236229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236229		asdfgrace	Fire (BOI24_fire)	C++20	100 / 100	90 ms	70332 KiB

Main

#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'));

/*
at most 1 is going to work overnight
n^3 sol:
dp[l][r] = minimum number from the left bound of l's to the right bound of r's
how will we sort them - just by left bound?
or i guess you start at a left bound and iterate over the right bounds
are we gonna assume we're using l and r? not necessarily sometimes the overlap
and you can just use 1 instead
if r ends before l ends
then you want to find the bounds for each r-value
which i guess you can do by sorting or smth
is 5000^2log too much for binary search & sorting
if no one works overnight
then we're also confined to a single possible starting point at 0
so if we can do that in n^2log we can do this in nlog
if all the intervals have the same length
then ???
also if B is entirely contained in A
then you would never ever use A

how about some kind of binary lift idk
like you start at i & greedily choose the available segment that takes you
as rightmost as possible (measured by right bound)
(the right bound is as far from this one's right bound as possible)

*/



int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n, m;
  cin >> n >> m;
  function<int(int, int)> dist = [&] (int x, int y) {
    if (y > x) return y - x;
    return y + m - x;
  };
  vector<array<int, 2>> a(n); vector<int> len(n);
  bool good = true;
  for (int i = 0; i < n; i++) {
    cin >> a[i][0] >> a[i][1];
    if (a[i][1] == 0) a[i][1] = m;
    if (a[i][1] < a[i][0]) good = false;
    len[i] = dist(a[i][0], a[i][1]);
  }
  sort(a.begin(), a.end(), [&] (array<int, 2> a1, array<int, 2> a2) {
    return a1[0] < a2[0] || (a1[0] == a2[0] && dist(a1[0], a1[1]) < dist(a2[0], a2[1]));
  });
  vector<bool> in(n, true);
  int mx = 0, lmx = 0;
  for (int i = 0; i < n; i++) {
    if (i < n - 1 && a[i][0] == a[i + 1][0]) {
      in[i] = false;
      continue;
    }
    if (a[i][0] < a[i][1]) {
      if (a[i][1] <= mx) in[i] = false;
      else mx = a[i][1];
    } else {
      mx = m;
      if (a[i][1] <= lmx) in[i] = false;
      else lmx = a[i][1];
    }
  }
  for (int i = 0; i < n; i++) {
    if (a[i][0] < a[i][1] && a[i][1] <= lmx) in[i] = false;
  }
  vector<array<int, 2>> na;
  for (int i = 0; i < n; i++) {
    if (in[i]) na.push_back(a[i]);
  }
  a = na;
  n = (int) a.size();
  parr2d(a);
  if (good && a[0][0] != 0) {
    cout << -1 << '\n';
  } else {
    vector<vector<array<long long, 2>>> next(20, vector<array<long long, 2>>(n));
    int it = 0;
    for (int i = 0; i < n; i++) {
      while (dist(a[i][0], a[(it + 1) % n][0]) <= dist(a[i][0], a[i][1])) it = (it + 1) % n;
      next[0][i][0] = it;
      if (i == it) {
        next[0][i][1] = 0;
      } else {
        next[0][i][1] = dist(a[i][1], a[it][1]);
      }
    }
    parr2d(next[0]);
    for (int j = 1; j < 20; j++) {
      for (int i = 0; i < n; i++) {
        next[j][i] = {next[j - 1][next[j - 1][i][0]][0],
            next[j - 1][i][1] + next[j - 1][next[j - 1][i][0]][1]};
      }
    }
    int ans = 1e9;
    for (int i = 0; i < n; i++) {
      pv(i);
      long long sum = dist(a[i][0], a[i][1]);
      int need = 1; int at = i; int lst_pos = a[i][0];
      for (int j = 19; j >= 0; j--) {
        if (sum + next[j][at][1] < m) {
          need += (1 << j);
          sum += next[j][at][1];
          at = next[j][at][0];
        }
      }
      need++;
      sum += next[0][at][1];
      at = next[0][at][0];
      if (sum >= m) {
        pv(need);
        ans = min(ans, need);
      }
    }
    cout << (ans == 1e9 ? -1 : ans) << '\n';
  }
}

• Subtask 1: 14 / 14
• Subtask 2: 17 / 17
• Subtask 3: 9 / 9
• Subtask 4: 13 / 13
• Subtask 5: 21 / 21
• Subtask 6: 26 / 26