Submission #1164292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164292		raspy	Event Hopping 2 (JOI21_event2)	C++20	100 / 100	226 ms	40516 KiB

event2

//
// Created by lukah on 09/03/2025.
//
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+5;
const int LOGN = 22;
const int INF = 1e9;

int L[N], R[N];
int bl[2*N][LOGN];
vector<int> pos[2*N];

int prestej(int l, int r)
{
  int rez = 0;
  for (int j = LOGN-1; j >= 0; j--)
    if (bl[l][j] <= r)
    {
      l = bl[l][j];
      rez += (1<<j);
    }
  return rez;
}

signed main()
{
  int n, k;
  cin >> n >> k;
  map<int, int> mp;
  for (int i = 0; i < n; i++)
  {
    cin >> L[i] >> R[i];
    mp[L[i]] = 1;mp[R[i]] = 1;
  }
  int cur_pos = 0;
  for (auto &[pos, val] : mp)
    val = cur_pos++;
  for (int i = 0; i < n; i++)
    L[i] = mp[L[i]], R[i] = mp[R[i]];
  for (int i = 0; i < n; i++)
    pos[L[i]].push_back(i);
  int cur_r = cur_pos;
  for (int i = cur_pos; i >= 0; i--)
  {
    for (int j = 0; j < pos[i].size(); j++)
      cur_r = min(cur_r, R[pos[i][j]]);
    bl[i][0] = cur_r;
  }
  for (int j = 1; j < LOGN; j++)
    for (int i = 0; i <= cur_pos; i++)
      bl[i][j] = bl[bl[i][j - 1]][j - 1];
  int cur_k = prestej(0, cur_pos-1);
  if (cur_k < k)
  {
    cout << "-1\n";
    return 0;
  }
  set<pair<int, int>> st;
  st.insert({0, 0});
  st.insert({cur_pos-1, cur_pos-1});
  int i = 0;
  while (st.size()-2 < k)
  {
    auto it = st.lower_bound({R[i], 0});
    int r = it->first;
    it--;
    int l = it->second;
    i++;
    if (l > L[i-1]) continue;
    int zac = cur_k - prestej(l, r) + prestej(l, L[i-1]) + prestej(R[i-1], r) + 1;
    if (zac >= k)
    {
      cout << i<< "\n";
      cur_k = zac;
      st.insert({L[i-1], R[i-1]});
    }
  }
  return 0;
}

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