Submission #871934

#	Time	Username	Problem	Language	Result	Execution time	Memory
871934		tvladm2009	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	210 ms	37332 KiB

event2

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = (int) 1e5 + 7;
const int K = 20;
pair<int, int> a[N];
int mx[2 * N], l[2 * N], dp[2 * N];
int tab[K][2 * N];
int n, k;

void build() {
  for (int i = 1; i <= 2 * n; i++) {
    tab[0][i] = l[i];
  }
  for (int k = 1; k < K; k++) {
    for (int i = 1; i <= 2 * n; i++) {
      tab[k][i] = tab[k - 1][tab[k - 1][i]];
    }
  }
}

int lift(int a, int x) {
  for (int k = 0; k < K; k++) {
    if (x & (1 << k)) {
      a = tab[k][a];
    }
  }
  return a;
}

bool check(int l, int r, int val) {
  if (val <= 0) {
    return true;
  }
  int nxt = lift(r, val);
  if (nxt != 2 * n && nxt >= l) {
    return true;
  } else {
    return false;
  }
}

int get(int l, int r) {
  return dp[r] - dp[l] - !check(l, r, dp[r] - dp[l]);
}

int main() {
#ifdef ONPC
  freopen("input.txt", "r", stdin);
#else
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif // ONPC

  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].first >> a[i].second;
  }

  {
    set<int> vals;
    unordered_map<int, int> mp;
    for (int i = 1; i <= n; i++) {
      vals.insert(a[i].first);
      vals.insert(a[i].second);
    }
    int id = 1;
    for (auto it = vals.begin(); it != vals.end(); it++) {
      mp[*it] = id;
      id++;
    }
    for (int i = 1; i <= n; i++) {
      a[i].first = mp[a[i].first];
      a[i].second = mp[a[i].second];
    }
  }

  for (int i = 1; i <= 2 * n; i++) {
    mx[i] = -1;
    l[i] = 2 * n;
  }
  for (int i = 1; i <= n; i++) {
    mx[a[i].second] = max(mx[a[i].second], a[i].first);
  }
  int cur = -1;
  for (int i = 1; i <= 2 * n; i++) {
    cur = max(cur, mx[i]);
    if (cur != -1) {
      l[i] = cur;
    }
  }
  for (int i = 1; i <= 2 * n; i++) {
    if (l[i] == 2 * n) {
      dp[i] = 0;
    } else {
      dp[i] = dp[l[i]] + 1;
    }
  }

  if (dp[2 * n] < k) {
    cout << "-1\n";
    return 0;
  }
  build();
  int maxsum = dp[2 * n];
  set<pair<int, int>> free;
  vector<int> sol;
  free.insert({1, 2 * n});
  for (int i = 1; i <= n; i++) {
    if ((int) sol.size() == k) {
      break;
    }
    int l = a[i].first, r = a[i].second;
    auto it = free.lower_bound({a[i].first + 1, 0});
    if (it == free.begin()) {
      continue;
    }
    it--;
    if (it->second < r) {
      continue;
    }
    int ll = it->first, rr = it->second;
    int before = get(ll, rr);
    int after = get(ll, l) + get(r, rr) + 1;
    if (maxsum + after - before >= k) {
      sol.push_back(i);
      free.erase(it);
      if (l > ll) {
        free.insert({ll, l});
      }
      if (r < rr) {
        free.insert({r, rr});
      }
      maxsum += after - before;
    } else {
      continue;
    }
  }
  for (auto &it : sol) {
    cout << it << "\n";
  }
  return 0;
}

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