Submission #397078

#	Time	Username	Problem	Language	Result	Execution time	Memory
397078		fedoseevtimofey	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	227 ms	25568 KiB

event2

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
#include <bitset>
#include <chrono>
 
using namespace std;
 
typedef long long ll;
 
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n, k;
  cin >> n >> k;
  vector <int> l(n), r(n);
  vector <int> c;
  for (int i = 0; i < n; ++i) {
    cin >> l[i] >> r[i];
    c.push_back(l[i]);
    c.push_back(r[i]);
  }
  sort(c.begin(), c.end());
  c.resize(unique(c.begin(), c.end()) - c.begin());
  for (int i = 0; i < n; ++i) {
    l[i] = lower_bound(c.begin(), c.end(), l[i]) - c.begin();
    r[i] = lower_bound(c.begin(), c.end(), r[i]) - c.begin();
  }
  int m = c.size();
  vector <int> nxt(m + 1, m);
  for (int i = 0; i < n; ++i) {
    nxt[l[i]] = min(nxt[l[i]], r[i]);
  }
  for (int i = m - 1; i >= 0; --i) {
    nxt[i] = min(nxt[i], nxt[i + 1]);
  }
  const int K = 20;
  vector <vector <int>> go(K, vector <int> (m + 1, m));
  go[0] = nxt;
  for (int j = 1; j < K; ++j) {
    for (int i = 0; i <= m; ++i) {
      go[j][i] = go[j - 1][go[j - 1][i]];
    }
  }
  auto get_cnt = [&] (int L, int R) {
    int can = 0;
    for (int i = K - 1; i >= 0; --i) {
      if (go[i][L] <= R) {
        can += (1 << i);
        L = go[i][L];
      }
    }
    return can;
  };
  if (get_cnt(0, m - 1) < k) {
    cout << "-1\n";
    return 0;
  }
  set <pair <int, int>> segs;
  segs.insert({-1, 0});
  segs.insert({m - 1, m});
  int cnt = get_cnt(0, m - 1);
  auto can_add = [&] (int L, int R) {
    int new_cnt = cnt;
    auto nx = segs.lower_bound({L, -1});
    int nL = nx->first;
    if (nL < R) return false; 
    auto pr = prev(nx);
    int pR = pr->second;
    if (pR > L) return false;
    new_cnt -= get_cnt(pR, nL);
    new_cnt += get_cnt(pR, L);
    new_cnt += get_cnt(R, nL);
    ++new_cnt;
    if (new_cnt >= k) {
      cnt = new_cnt;
      segs.insert({L, R});
      return true;
    } else {
      return false;
    }
  };
  vector <int> ans;
  for (int i = 0; i < n; ++i) {
    if (ans.size() < k && can_add(l[i], r[i])) {
      ans.push_back(i);
    }
  }
  for (auto x : ans) {
    cout << x + 1 << '\n';
  }
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:102:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  102 |     if (ans.size() < k && can_add(l[i], r[i])) {
      |         ~~~~~~~~~~~^~~

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