Submission #474452

#	Time	Username	Problem	Language	Result	Execution time	Memory
474452		Pety	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	272 ms	23960 KiB

event2

#include <bits/stdc++.h>
#define ll long long
#define ld long double

using namespace std;

int n, k, dp[20][200004];
pair<int, int>event[100002];

int dist (int l, int r) {
  l = max(0, l);
  int ans = 0;
  for (int i = 18; i >= 0; i--) {
    if (dp[i][l] <= r) {
      l = dp[i][l];
      ans += (1 << i);
    }
  }
  return ans;
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n >> k;
  vector<int>norm;
  for (int i = 1; i <= n; i++)  {
    int a, b;
    cin >> a >> b;
    event[i] = {a, b};
    norm.push_back(a);
    norm.push_back(b);
  }
  sort(norm.begin(), norm.end());
  int aux = 0;
  for (int i = 0; i < norm.size(); i++) {
    if (i == 0 || norm[i - 1] != norm[i]) {
      norm[aux++] = norm[i];
    }
  }
  norm.resize(aux);
  for (int i = 0; i < aux + 1; i++) {
    dp[0][i] = aux + 1;
  }
  for (int i = 0; i <= 18; i++)
    dp[i][aux + 1] = aux + 1;
  for (int i = 1; i <= n; i++) {
    event[i].first = lower_bound(norm.begin(), norm.end(), event[i].first) - norm.begin();
    event[i].second = lower_bound(norm.begin(), norm.end(), event[i].second) - norm.begin();
    dp[0][event[i].first] = min(dp[0][event[i].first], event[i].second); 
  }
  for (int i = aux - 1; i >= 0; i--) {
    dp[0][i] = min(dp[0][i], dp[0][i + 1]);
    for (int j = 1; j <= 18; j++) {
      dp[j][i] = dp[j - 1][dp[j - 1][i]];
    }
  }
  set<pair<int, int> > s;
  s.insert({-1, -1});
  s.insert({aux, aux});
  int sum = dist(0, aux - 1);
  int newsum;
  vector<int>ans;
  for (int i = 1; i <= n; i++) {
    pair<int, int>p = event[i];
    auto it = s.lower_bound({p.first, 0});
    auto it2 = it;
    it2--;
    if (p.second > it->first || p.first < it2->second)
      continue;

    newsum = sum - dist(it2->second, it->first) + dist(it2->second, p.first) + dist(p.second, it->first) + 1;
    if (newsum >= k) {
      s.insert(p);
      sum = newsum;
      ans.push_back(i);
    }
    if (ans.size() == k)
     break; 
  }
  if ( ans.size() == k)
    for (auto it : ans) {
      cout << it << "\n";
    }
  else 
    cout << "-1\n";
  return 0;
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:37:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for (int i = 0; i < norm.size(); i++) {
      |                   ~~^~~~~~~~~~~~~
event2.cpp:79:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |     if (ans.size() == k)
      |         ~~~~~~~~~~~^~~~
event2.cpp:82:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |   if ( ans.size() == k)
      |        ~~~~~~~~~~~^~~~

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