제출 #1164910

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164910		fryingduc	Event Hopping 2 (JOI21_event2)	C++20	100 / 100	121 ms	22164 KiB

event2

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e5 + 5;
const int N = 2e5 + 5;
const int LG = 18;
int n, k, l[maxn], r[maxn];
int up[N][LG + 1];

void solve() {
  cin >> n >> k;
  vector<int> compress;
  for (int i = 1; i <= n; ++i) {
    cin >> l[i] >> r[i];
    compress.push_back(l[i]);
    compress.push_back(r[i]);
  }
  sort(compress.begin(), compress.end());
  compress.erase(unique(compress.begin(), compress.end()), compress.end());
  int m = (int)compress.size();
  for (int i = 1; i <= m + 1; ++i) {
    up[i][0] = m + 1;
  }
  for (int i = 1; i <= n; ++i) {
    l[i] = lower_bound(compress.begin(), compress.end(), l[i]) - compress.begin() + 1;
    r[i] = lower_bound(compress.begin(), compress.end(), r[i]) - compress.begin() + 1;
    up[l[i]][0] = min(up[l[i]][0], r[i]);
  }
  for (int i = m; i; --i) {
    up[i][0] = min(up[i][0], up[i + 1][0]);
  }
  for (int i = 1; i <= LG; ++i) {
    for (int u = 1; u <= m + 1; ++u) {
      up[u][i] = up[up[u][i - 1]][i - 1];
    }
  }
  set<pair<int, int>> s;
  auto valid_insert = [&](int cl, int cr) {
    auto it = s.lower_bound(make_pair(cl, cr));
    if (it != s.end() and it->first < cr) return 0;
    if (it != s.begin() and prev(it)->second > cl) return 0;
    return 1;
  };
  auto calc = [&](int l, int r) {
    int res = 0;
    for (int i = LG; i >= 0; --i) {
      if (up[l][i] <= r) {
        res += (1 << i);
        l = up[l][i];
      }
    }
    return res;
  };
  int res = calc(1, m);
  if (res < k) {
    cout << -1;
    return;
  }
  vector<int> cand;
  for (int i = 1; i <= n; ++i) {
    if ((int)cand.size() == k) break;
//    debug(l[i], r[i]);
    if (!valid_insert(l[i], r[i])) continue;
    auto it = s.lower_bound(make_pair(l[i], r[i]));
    int br = (it == s.end() ? m : it->first);
    int bl = (it == s.begin() ? 1 : prev(it)->second);
    int cur = res - calc(bl, br) + calc(bl, l[i]) + calc(r[i], br);
//    debug(bl, l[i], r[i], br);
//    debug(cur, calc(bl, br), calc(bl, l[i]), calc(r[i], br));
    if (cur + 1 >= k - (int)cand.size()) {
      s.insert(make_pair(l[i], r[i]));
      cand.push_back(i);
      res = cur;
    }
  }
  for (auto i:cand) cout << i << '\n';
}

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

  solve();

  return 0;
}

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