oj.uz

Submission #955609

# Submission time Handle Problem Language Result Execution time Memory
955609 2024-03-31T06:07:19 Z abczz Event Hopping 2 (JOI21_event2) C++14
0 / 100
 73 ms 39432 KB 
#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;
array <ll, 3> R[200001];

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];
}

void dfs(ll u) {
  s = max(s, mxdepth[u]);
  for (auto v : adj[u]) {
    mxdepth[v] = mxdepth[u] + 1;
    dfs(v);
  }
}

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;
  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();
        adj[i].push_back(id);
        if (l > x) {
          x = l;
          y = id;
        }
      }
      else break;
    }
    bl[i][0] = y;
    D[i] = D[y]+1;
    pq.push({R[i][1], R[i][0], i});
  }
  while (!pq.empty()) {
    auto [r, l, id] = pq.top();
    pq.pop();
    adj[n].push_back(id);
  }
  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]);
    //cout << y << " " << z << endl;
    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

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Correct 3 ms 11612 KB Output is correct
3 Correct 3 ms 11752 KB Output is correct
4 Incorrect 73 ms 39432 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11608 KB Output is correct
2 Correct 3 ms 11612 KB Output is correct
3 Correct 2 ms 11612 KB Output is correct
4 Correct 2 ms 11612 KB Output is correct
5 Correct 2 ms 11612 KB Output is correct
6 Correct 2 ms 11612 KB Output is correct
7 Incorrect 3 ms 11612 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11608 KB Output is correct
2 Correct 3 ms 11612 KB Output is correct
3 Correct 2 ms 11612 KB Output is correct
4 Correct 2 ms 11612 KB Output is correct
5 Correct 2 ms 11612 KB Output is correct
6 Correct 2 ms 11612 KB Output is correct
7 Incorrect 3 ms 11612 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11612 KB Output is correct
2 Correct 3 ms 11612 KB Output is correct
3 Correct 3 ms 11752 KB Output is correct
4 Incorrect 73 ms 39432 KB Output isn't correct
5 Halted 0 ms 0 KB -