Submission #955638

#	Time	Username	Problem	Language	Result	Execution time	Memory
955638		abczz	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	174 ms	52760 KiB

event2

#include <iostream>
#include <array>
#include <algorithm>
#include <queue>
#include <map>
#define ll long long

using namespace std;

vector <ll> adj[200001], V;
ll n, k, x, y, s, z, X[200001], bl[200001][18], D[200001], mxdepth[200001];
map <ll, array<ll, 3>> mp;
priority_queue <array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>> > pq;
priority_queue <array<ll, 3>> pq2;
array <ll, 3> R[200001], L[200001];

void dfs(ll u) {
  s = max(s, mxdepth[u]);
  for (auto v : adj[u]) {
    mxdepth[v] = mxdepth[u] + 1;
    dfs(v);
  }
}
ll binlift(ll u, ll r) {
  ll du = D[u];
  for (int i=17; i>=0; --i) {
    if (r <= R[bl[u][i]][0] && bl[u][i] != n) {
      u = bl[u][i];
    }
  }
  return du-D[u];
}

int main() {
  cin >> n >> k;
  for (int i=0; i<n; ++i) {
    cin >> R[i][0] >> R[i][1];
    R[i][2] = i;
  }
  sort(R, R+n);
  for (int i=0; i<n; ++i) {
    X[R[i][2]] = i;
    L[i] = R[i];
    L[i][2] = i;
  }
  sort(L, L+n, [](auto a, auto b) {
    return a[1] > b[1];
  });
  x = -1e18, y = n;
  for (int i=0; i<n; ++i) {
    while (!pq.empty()) {
      auto [r, l, id] = pq.top();
      if (r <= R[i][0]) {
        pq.pop();
        if (l > x) {
          x = l;
          y = id;
        }
      }
      else break;
    }
    //cout << y << " " << i << " " << R[i][0] << " " << R[i][1] << '\n';
    bl[i][0] = y;
    D[i] = D[y]+1;
    pq.push({R[i][1], R[i][0], i});
  }
  bl[n][0] = n;
  for (int j=1; j<18; ++j) {
    for (int i=0; i<=n; ++i) {
      bl[i][j] = bl[bl[i][j-1]][j-1];
    }
  }
  while (!pq.empty()) {
    auto [r, l, id] = pq.top();
    pq.pop();
    adj[n].push_back(id);
  }
  x = 1e18, y = n;
  for (int i=0; i<n; ++i) {
    while (!pq2.empty()) {
      auto [l, r, id] = pq2.top();
      if (L[i][1] <= l) {
        pq2.pop();
        if (x > r) {
          x = r;
          y = id;
        }
      }
      else break;
    }
    adj[y].push_back(L[i][2]);
    pq2.push({L[i][0], L[i][1], L[i][2]});
  }
  dfs(n);
  if (s < k) {
    cout << "-1\n";
    return 0;
  }
  mp[0] = {0, s, n};
  for (int j=0; j<n; ++j) {
    int i = X[j];
    auto it = mp.lower_bound(R[i][1]);
    if (it != mp.end()) z = binlift(it->second[2], R[i][1]);
    else z = mxdepth[i]-1;
    it = prev(it);
    if (it->second[0] > R[i][0]) continue;
    x = it->second[1];
    y = binlift(i, it->second[0]);
    if (s-x+y+z+1 >= k) {
      s = s-x+y+z+1;
      mp[it->first] = {it->second[0], y, it->second[2]};
      mp[R[i][0]] = {R[i][1], z, i};
      V.push_back(j);
    }
  }
  for (int i=0; i<k; ++i) {
    cout << V[i]+1 << '\n';
  }
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:52:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |       auto [r, l, id] = pq.top();
      |            ^
event2.cpp:74:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |     auto [r, l, id] = pq.top();
      |          ^
event2.cpp:81:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |       auto [l, r, id] = pq2.top();
      |            ^

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