Submission #1256948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256948		LucaLucaM	Event Hopping 2 (JOI21_event2)	C++20	100 / 100	115 ms	23236 KiB

event2

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <set>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

const int LGMAX = 17;

struct Interval {
  int l, r;
  Interval() {}
  Interval(int _l, int _r) : l(_l), r(_r) {}
  bool operator < (const Interval  &other) const {
    return l != other.l? l < other.l : r < other.r; 
  }
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);

  int n, k;
  std::cin >> n >> k;

  std::vector<Interval> a(n); 
  std::vector<int> norm;

  for (auto &[l, r] : a) {
    std::cin >> l >> r;
    norm.push_back(l);
    norm.push_back(r);
  }

  std::sort(norm.begin(), norm.end());
  norm.erase(std::unique(norm.begin(), norm.end()), norm.end());

  for (auto &[l, r] : a) {
    l = std::lower_bound(norm.begin(), norm.end(), l) - norm.begin() + 1;
    r = std::lower_bound(norm.begin(), norm.end(), r) - norm.begin() + 1;
  }

  std::vector<Interval> b = a;
  std::sort(b.begin(), b.end(), [](Interval x, Interval y) {
    return x.r < y.r;
  });

  std::vector<int> next(2 * n + 5, 2 * n + 4);
  std::vector<std::vector<int>> jump(LGMAX + 1, std::vector<int>(2 * n + 5));

  for (const auto &[l, r] : a) {
    next[l] = std::min(next[l], r);
  }
  for (int i = 2 * n; i >= 0; i--) {
    next[i] = std::min(next[i], next[i + 1]);
  }

  for (int i = 0; i < 2 * n + 5; i++) {
    jump[0][i] = next[i];
  }
  for (int j = 1; j <= LGMAX; j++) {
    for (int i = 0; i < 2 * n + 5; i++) {
      jump[j][i] = jump[j - 1][jump[j - 1][i]];
    }
  }

  auto query = [&](int l, int r) {
    int ret = 0;
    int p = l;
    for (int k = LGMAX; k >= 0; k--) {
      if (jump[k][p] <= r) {
        ret += (1 << k);
        p = jump[k][p];
      }
    }
    return ret;
  };

  int maxv = 2 * n;

  int can = query(1, maxv);

  if (can < k) {
    std::cout << -1;
    return 0;
  }

  std::set<Interval> st;
  st.insert({0, 0});
  st.insert({maxv + 1, maxv + 1});

  std::vector<int> answer;

  for (int i = 0; i < n; i++) {
    auto [l, r] = a[i];
    auto lt = st.lower_bound({l, 0});
    --lt;
    auto dr = lt;
    ++dr;
    if (lt -> r <= l && r <= dr -> l) {
      int newCan = can - query(lt -> r, dr -> l) + query(lt -> r, l) + query(r, dr -> l) + 1;
      if (newCan >= k) {
        can = newCan;
        answer.push_back(i);
        st.insert({l, r});
      }
    }
  }

  assert((int) answer.size() >= k);
  answer.resize(k);
  for (int x : answer) {
    std::cout << x + 1 << '\n';
  }
  
  return 0;
}

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