Submission #1038606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038606		juicy	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	93 ms	22132 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) {
  if (r == n + 2) {
    return 0;
  }
  if (l == -1) {
    return 1;
  }
  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;
}

array<int, 2> cur{};
set<int> st[2];

bool add(int u, set<int> &st, int &cur) {
  if (!st.size()) {
    return 0;
  }
  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[0].insert(0);
  st[0].insert(n + 1);
  cur[0] = qry(0, n + 1);
  if (cur[0] < k) {
    cout << -1;
    exit(0);
  }
  bool flg = 0;
  vector<int> res;
  for (int i = 1; i <= n && res.size() < k; ++i) {
    if (!flg && res.size() == k - 2) {
      st[1] = st[0];
      cur[1] = cur[0];
      st[0].erase(n + 1);
      cur[0] -= qry(*st[0].rbegin(), n + 1);
      st[0].insert(n + 2);
      st[1].erase(0);
      cur[1] -= qry(0, *st[1].begin()) - 1;
      st[1].insert(-1);
      flg = 1;
    }
    if (!flg) {
      if (add(pos[i], st[0], cur[0])) {
        res.push_back(i);
      }
    } else {
      bool A = add(pos[i], st[0], cur[0]), B = add(pos[i], st[1], cur[1]);
      if (A || B) {
        if (!A) {
          st[0].clear();
        }
        if (!B) {
          st[1].clear();
        }
        res.push_back(i);
      }
    }
  }
  assert(res.size() == k);
  for (int x : res) {
    cout << x << "\n";
  }
  return 0;
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:107:40: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |   for (int i = 1; i <= n && res.size() < k; ++i) {
      |                             ~~~~~~~~~~~^~~
event2.cpp:108:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  108 |     if (!flg && res.size() == k - 2) {
      |                 ~~~~~~~~~~~^~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from event2.cpp:1:
event2.cpp:136:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  136 |   assert(res.size() == k);
      |          ~~~~~~~~~~~^~~~

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