Submission #1038613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038613		juicy	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	93 ms	16376 KiB

event2

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5, LG = 17, inf = 1e9 + 7;

int n, k;
int lt[N], rt[N], nxt[LG][N], pos[N];
array<int, 3> a[N];

int qry(int l, int r) {
  int res = r != n + 1;
  for (int i = LG - 1; ~i; --i) {
    if (nxt[i][l] != n + 1 && a[nxt[i][l]][1] <= a[r][0]) {
      l = nxt[i][l];
      res += 1 << i;
    }
  }
  return res;
}

int cur;
set<int> st;

bool add(int u) {
  auto it = st.lower_bound(u);
  int l = *prev(it), r = *it;
  if (l != -1 && a[l][1] > a[u][0]) {
    return 0;
  }
  if (r != n + 2 && a[u][1] > a[r][0]) {
    return 0;
  }
  int tmp = cur - qry(l, r) + qry(l, u) + qry(u, r);
  if (tmp < k) {
    return 0;
  }
  cur = tmp;
  st.insert(u);
  return 1;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> k;
  if (k == 1) {
    cout << 1;
    exit(0);
  }
  for (int i = 1; i <= n; ++i) {
    cin >> lt[i] >> rt[i];
    a[i] = {lt[i], rt[i], i};
  }  
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; ++i) {
    pos[a[i][2]] = i;
  }
  vector<int> ord(n + 1); iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int i, int j) {
    return a[i][1] > a[j][1];
  });
  int j = n, best = n + 1;
  a[n + 1] = {inf, inf, n + 1};
  for (int u : ord) {
    while (j > 0 && a[j][0] >= a[u][1]) {
      if (a[best][1] > a[j][1]) {
        best = j;
      }
      --j;
    }
    nxt[0][u] = best;
  }
  for (int j = 1; j < LG; ++j) {
    for (int i = 0; i <= n; ++i) {
      if (nxt[j - 1][i] == n + 1) {
        nxt[j][i] = n + 1;
      } else {
        nxt[j][i] = nxt[j - 1][nxt[j - 1][i]];
      }
    }
  }
  st.insert(0);
  st.insert(n + 1);
  cur = qry(0, n + 1);
  if (cur < k) {
    cout << -1;
    exit(0);
  }
  for (int i = 1, j = 1; i <= n && j <= k; ++i) {
    if (add(pos[i])) {
      cout << i << "\n";
      ++j;
    }
  }
  return 0;
}

// dumb?

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