Submission #389223

#	Time	Username	Problem	Language	Result	Execution time	Memory
389223		rama_pang	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	234 ms	25732 KiB

event2

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

int main() {
  ios::sync_with_stdio(0);
  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];
  }

  { // Coordinate Compression
    vector<int> coords;
    for (int i = 0; i < N; i++) {
      coords.emplace_back(L[i]);
      coords.emplace_back(R[i]);
    }
    sort(begin(coords), end(coords));
    coords.resize(unique(begin(coords), end(coords)) - begin(coords));
    for (int i = 0; i < N; i++) {
      L[i] = lower_bound(begin(coords), end(coords), L[i]) - begin(coords);
      R[i] = lower_bound(begin(coords), end(coords), R[i]) - begin(coords);
    }
  }

  const int LOG = 17;
  vector<vector<int>> dp(LOG, vector<int>(2 * N + 2, 2 * N + 1));
  for (int i = 0; i < N; i++) {
    dp[0][L[i]] = min(dp[0][L[i]], R[i]);
  }
  for (int i = 2 * N - 1; i >= 0; i--) {
    dp[0][i] = min(dp[0][i], dp[0][i + 1]);
  }
  for (int j = 1; j < LOG; j++) {
    for (int i = 0; i <= 2 * N; i++) {
      dp[j][i] = dp[j - 1][dp[j - 1][i]];
    }
  }
  const auto GetDP = [&](int L, int R) { // dp[L, R)
    int ans = 0;
    for (int j = LOG - 1; j >= 0; j--) {
      if (dp[j][L] <= R) {
        L = dp[j][L];
        ans |= 1 << j;
      }
    }
    return ans;
  };

  if (GetDP(0, 2 * N) < K) {
    cout << -1 << '\n';
    return 0;
  }

  vector<int> ans;
  set<int> active = {-1, 2 * N};
  for (int i = 0, curDP = GetDP(0, 2 * N - 1); i < N && ans.size() < K; i++) {
    if (*active.lower_bound(L[i]) < R[i]) continue;

    int loL = *prev(active.lower_bound(L[i])) + 1;
    int hiL = L[i];

    int loR = R[i];
    int hiR = *active.lower_bound(R[i]);

    int newDP = curDP - GetDP(loL, hiR) + GetDP(loL, hiL) + GetDP(loR, hiR) + 1;

    if (newDP >= K) {
      curDP = newDP;
      ans.emplace_back(i);
      for (int j = L[i]; j < R[i]; j++) {
        active.emplace(j);
      }
    }
  }

  assert(ans.size() == K);
  for (auto i : ans) {
    cout << i + 1 << '\n';
  }
  return 0;
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:61:68: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |   for (int i = 0, curDP = GetDP(0, 2 * N - 1); i < N && ans.size() < K; i++) {
      |                                                         ~~~~~~~~~~~^~~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from event2.cpp:1:
event2.cpp:81:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |   assert(ans.size() == K);
      |          ~~~~~~~~~~~^~~~

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