Submission #697337

#	Time	Username	Problem	Language	Result	Execution time	Memory
697337		peijar	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	224 ms	51696 KiB

event2

#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 MAXN = 2e5 + 1;
const int MAXP = 20;

int nxt[MAXP][MAXN];

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

  int nbInt, nbVoulus;
  cin >> nbInt >> nbVoulus;

  vector<pair<int, int>> intervalles(nbInt);
  vector<int> vals;
  for (auto &[L, R] : intervalles) {
    cin >> L >> R;
    vals.push_back(L);
    vals.push_back(R);
  }
  sort(vals.begin(), vals.end());
  vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
  int nbVals = vals.size();

  vector<vector<int>> onVal(nbVals);
  for (auto &[l, r] : intervalles) {
    l = lower_bound(vals.begin(), vals.end(), l) - vals.begin();
    r = lower_bound(vals.begin(), vals.end(), r) - vals.begin();
    onVal[l].push_back(r);
  }
  nxt[0][nbVals] = nbVals;
  for (int iVal = nbVals - 1; iVal >= 0; --iVal) {
    nxt[0][iVal] = nxt[0][iVal + 1];
    for (auto r : onVal[iVal])
      nxt[0][iVal] = min(nxt[0][iVal], r);
  }

  for (int p = 0; p < MAXP - 1; ++p)
    for (int i = 0; i <= nbVals; ++i)
      nxt[p + 1][i] = nxt[p][nxt[p][i]];

  auto calcMax = [&](int L, int R) {
    int sol = 0;
    for (int p = MAXP - 1; p >= 0; --p)
      if (nxt[p][L] <= R)
        sol += 1 << p, L = nxt[p][L];
    return sol;
  };
  if (calcMax(0, nbVals - 1) < nbVoulus) {
    cout << -1 << endl;
    return 0;
  }
  set<pair<int, int>> libre;
  libre.emplace(0, nbVals - 1);
  vector<int> sol;
  int tot = calcMax(0, nbVals - 1);
  for (int i = 0; i < nbInt and (int) sol.size() < nbVoulus; ++i) {
    auto [l, r] = intervalles[i];
    auto it = libre.upper_bound({l, (int)1e18});
    if (it == libre.begin())
      continue;
    --it;
    if (it->second < r)
      continue;
    auto [L, R] = *it;
    int nouv = tot - calcMax(L, R) + calcMax(L, l) + calcMax(r, R) + 1;
    if (nouv >= nbVoulus) {
      libre.erase(it);
      tot -= calcMax(L, R);
      libre.emplace(L, l);
      libre.emplace(r, R);
      tot = nouv;
      sol.push_back(i);
    }
  }
  for (int x : sol)
    cout << x + 1 << '\n';
}

• Subtask 1: 7 / 7
• Subtask 2: 1 / 1
• Subtask 3: 31 / 31
• Subtask 4: 61 / 61