Submission #727350

#	Time	Username	Problem	Language	Result	Execution time	Memory
727350		peijar	Event Hopping (BOI22_events)	C++17	100 / 100	200 ms	28432 KiB

events

#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int MAXP = 20;

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbInt, nbRequetes;
  cin >> nbInt >> nbRequetes;

  vector<pair<int, int>> intervalles(nbInt);
  vector<int> valeurs;
  for (auto &[l, r] : intervalles) {
    cin >> l >> r;
    valeurs.push_back(l);
    valeurs.push_back(r);
  }

  sort(valeurs.begin(), valeurs.end());
  valeurs.resize(unique(valeurs.begin(), valeurs.end()) - valeurs.begin());
  for (auto &[l, r] : intervalles) {
    l = lower_bound(valeurs.begin(), valeurs.end(), l) - valeurs.begin();
    r = lower_bound(valeurs.begin(), valeurs.end(), r) - valeurs.begin();
  }

  array<vector<int>, MAXP> prv;
  for (int p = 0; p < MAXP; ++p)
    prv[p].resize(nbInt);

  int deb = 1;
  int nbValeurs = valeurs.size();
  while (deb < nbValeurs)
    deb *= 2;
  vector<pair<int, int>> seg(2 * deb, pair(1e18, 1e18));
  for (int i = 0; i < nbInt; ++i) {
    auto [l, r] = intervalles[i];
    seg[deb + r] = min(seg[deb + r], pair(l, i));
  }
  for (int i = deb - 1; i; --i)
    seg[i] = min(seg[2 * i], seg[2 * i + 1]);

  auto query = [&](int l, int r) { // [l, r)
    l += deb, r += deb;
    pair<int, int> sol(1e18, 1e18);
    while (l < r) {
      if (l % 2)
        sol = min(sol, seg[l++]);
      if (r % 2)
        sol = min(sol, seg[--r]);
      l /= 2;
      r /= 2;
    }
    return sol.second;
  };
  for (int i = 0; i < nbInt; ++i) {
    auto [l, r] = intervalles[i];
    prv[0][i] = query(l, r + 1);
    // dbg(l, r, prv[0][i]);
  }
  dbg(prv[0]);
  for (int p = 0; p < MAXP - 1; ++p)
    for (int i = 0; i < nbInt; ++i)
      prv[p + 1][i] = prv[p][prv[p][i]];

  for (int iRequete = 0; iRequete < nbRequetes; ++iRequete) {
    int debut, fin;
    cin >> debut >> fin;

    --debut, --fin;
    if (debut == fin) {
      cout << 0 << '\n';
      continue;
    }
    int sol = 0;
    for (int p = MAXP - 1; p >= 0; --p)
      if (intervalles[prv[p][fin]].first > intervalles[debut].second)
        sol += 1 << p, fin = prv[p][fin];
    dbg(sol);
    auto [l, r] = intervalles[fin];
    if (intervalles[debut].second >= l and intervalles[debut].second <= r) {
      cout << sol + 1 << '\n';
      continue;
    }
    sol++;
    fin = prv[0][fin];
    if (intervalles[fin].first > intervalles[debut].second or
        intervalles[fin].second < intervalles[debut].second)
      cout << "impossible\n";
    else
      cout << sol + 1 << '\n';
  }
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30