Submission #594488

#	Time	Username	Problem	Language	Result	Execution time	Memory
594488		SuffixAutomata	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	169 ms	18108 KiB

event2

#include <bits/stdc++.h>
using namespace std;

#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using ll = long long;
using pii = pair<int, int>;
//#define int ll
const int MOD = 1000000007;

int l[100005], r[100005], mir[100005];
int nex[18][100005];
vector<pii> ls;
int n, k;

int qry(int L, int R) {
  int c = lower_bound(all(ls), pii{L, -1})->se, x = 1;

  // cout << c << ' ' << mir[c] << endl;
  c = mir[c];
  if (r[c] > R)
    return 0;
  // cout << c << endl;
  for (int i = 17; i >= 0; i--)
    if (r[nex[i][c]] <= R)
      c = nex[i][c], x += (1 << i);
  return x;
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> k;
  vector<pii> evt1;
  for (int i = 1; i <= n; i++) {
    cin >> l[i] >> r[i];
    evt1.pb({l[i], i});
    evt1.pb({r[i], -i});
    ls.pb({l[i], i});
  }
  ls.pb({2e9, 0});
  sort(all(evt1));
  sort(all(ls));
  pii x = {2e9, 0}, cr = {2e9, 0};
  r[0] = (int)(2e9) + 1;
  while (evt1.size()) {
    int p = evt1.back().se;
    evt1.pop_back();
    if (p < 0)
      nex[0][-p] = x.se;
    else {
      x = min(x, {r[p], p});
      cr = min(cr, {r[p], p});
      mir[p] = cr.se;
    }
  }
  for (int j = 1; j < 18; j++)
    for (int i = 1; i <= n; i++)
      nex[j][i] = nex[j - 1][nex[j - 1][i]];
  // while (1) {
  //   int l, r;
  //   cin >> l >> r;
  //   cout << qry(l, r) << endl;
  // }
  int cur = qry(0, 2e9);
  // cout << cur << endl;
  if (cur < k) {
    cout << -1 << endl;
    return 0;
  }
  set<pii> borders;
  borders.insert({-1, 0});
  borders.insert({2e9, (int)(2e9) + 1});
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    int cl = l[i], cr = r[i];
    auto it = prev(borders.lower_bound({cr, -1}));
    if (max(it->fi, cl) < min(it->se, cr))
      continue;
    auto it2 = next(it);
    int test =
        cur - qry(it->se, it2->fi) + qry(it->se, cl) + qry(cr, it2->fi) + 1;
    if (test >= k) {
      borders.insert({cl, cr});
      cur = test, cnt++;
      cout << i << "\n";
      if (cnt == k)
        break;
    }
  }
  return 0;
}

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