Submission #554573

#	Time	Username	Problem	Language	Result	Execution time	Memory
554573		MilosMilutinovic	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	271 ms	29640 KiB

event2

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, k;
  cin >> n >> k;
  vector<int> l(n), r(n);
  for (int i = 0; i < n; i++) {
    cin >> l[i] >> r[i];
    --r[i];
  }
  vector<int> xs;
  for (int i = 0; i < n; i++) {
    xs.push_back(l[i]);
    xs.push_back(r[i]);
  }
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  for (int i = 0; i < n; i++) {
    l[i] = lower_bound(xs.begin(), xs.end(), l[i]) - xs.begin();
    r[i] = lower_bound(xs.begin(), xs.end(), r[i]) - xs.begin();
  }                                             
  int sz = xs.size();
  const int LOG = 20;
  vector<vector<int>> nxt(sz, vector<int>(LOG, 1e9));
  for (int i = 0; i < n; i++) {
    nxt[l[i]][0] = min(nxt[l[i]][0], r[i]);
  }
  for (int i = sz - 1; i > 0; i--) {
    nxt[i - 1][0] = min(nxt[i - 1][0], nxt[i][0]);
  }
  for (int j = 1; j < LOG; j++) {
    for (int i = 0; i < sz; i++) {
      if (nxt[i][j - 1] + 1 < sz) {
        nxt[i][j] = nxt[nxt[i][j - 1] + 1][j - 1]; 
      }
    }
  }
  map<int, int> mp;
  mp[0] = sz - 1;
  int cc;
  auto Count = [&](int L, int R) {                  
    int cnt = 0;
    for (int j = LOG - 1; j >= 0; j--) {
      if (L < sz && nxt[L][j] <= R) {
        cnt += (1 << j);
        L = nxt[L][j] + 1;
      }
    }
    return cnt;
  };
  cc = Count(0, sz - 1);     
  function<void(int, int)> Cut = [&](int L, int R) {
    auto it = prev(mp.lower_bound(L + 1));
    cc -= Count(it->first, it->second);
    int xl = it->first;
    int xr = it->second;
    mp.erase(it);
    if (xl != L) {
      cc += Count(xl, L - 1);
      mp[xl] = L - 1;
    }
    if (xr != R) {
      cc += Count(R + 1, xr);
      mp[R + 1] = xr;
    }
  };
  function<void(int, int)> Update = [&](int L, int R) {
    {
      auto it = mp.lower_bound(L);
      if (it != mp.begin() && prev(it)->second == L - 1) {
        cc -= Count(prev(it)->first, prev(it)->second);
        L = prev(it)->first;  
        mp.erase(prev(it));
      }
    }
    {
      auto it = mp.lower_bound(R + 1);
      if (it != mp.end() && it->first == R + 1) {
        cc -= Count(it->first, it->second);
        R = it->second;
        mp.erase(it);
      }
    }
    mp[L] = R;
    cc += Count(L, R);
  };
  auto Check = [&](int L, int R) {
    auto it = mp.lower_bound(L + 1);
    if (it == mp.begin()) {
      return false;
    }
    it = prev(it);
    return it->first <= L && R <= it->second;
  };
  vector<int> ans;
  for (int i = 0; i < n; i++) {
    if (!Check(l[i], r[i])) {
      continue;
    }
    Cut(l[i], r[i]);
    if (cc >= k - ans.size() - 1) {
      ans.push_back(i);
    } else {
      Update(l[i], r[i]);
    }                     
    auto it = mp.begin(); 
    while (it != mp.end()) {
      it = next(it);
    } 
  }
  if (ans.size() < k) {
    cout << -1 << '\n';
  } else {
    for (int i = 0; i < k; i++) {
      cout << ans[i] + 1 << '\n';
    }
  }
  return 0;
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:105:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     if (cc >= k - ans.size() - 1) {
      |         ~~~^~~~~~~~~~~~~~~~~~~~~
event2.cpp:115:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  115 |   if (ans.size() < k) {
      |       ~~~~~~~~~~~^~~

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