Submission #1256934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256934		LucaLucaM	Event Hopping 2 (JOI21_event2)	C++20	1 / 100	3092 ms	2500 KiB

event2

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

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

const int INF = 1e9;

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

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

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

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

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

  auto query = [&](int l, int r) {
    int ret = 0;
    int p = l;
    for (const auto &[x, y] : b) {
      if (p <= x && y <= r) {
        p = y;
        ret++;
      }
    }
    return ret;
  };

  int can = query(1, INF);

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

  std::set<Interval> st;
  st.insert({-1, -1});
  st.insert({INF + 1, INF + 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) {
        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: 0 / 7
• Subtask 2: 1 / 1
• Subtask 3: 0 / 31
• Subtask 4: 0 / 61