oj.uz

Submission #929858

# Submission time Handle Problem Language Result Execution time Memory
929858 2024-02-18T08:23:00 Z Pannda Event Hopping 2 (JOI21_event2) C++17
0 / 100
 187 ms 51276 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 12345;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<array<int, 2>> a(n);
    set<array<int, 2>> existed;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        a[i] = {l, r};
        if (existed.count(a[i])) {
            a[i] = {-INF + 1, INF - 1};
        } else {
            existed.insert(a[i]);
        }
    }

    auto [next, prev] = [](int n, vector<array<int, 2>> a) {
        int log = 32 - __builtin_clz(n);
        vector<vector<int>> next(n, vector<int>(log, -1));
        vector<vector<int>> prev(n, vector<int>(log, -1));
        vector<array<int, 3>> events;
        for (int i = 0; i < n; i++) {
            events.push_back({ a[i][0], +1, i });
            events.push_back({ a[i][1], -1, i });
        }
        sort(events.begin(), events.end());
        priority_queue<array<int, 2>, vector<array<int, 2>>, less<>> mx_pq;
        for (auto [x, type, i] : events) {
            if (type == -1) {
                mx_pq.push({ a[i][0], i });
            } else {
                prev[i][0] = mx_pq.empty() ? -1 : mx_pq.top()[1];
            }
        }
        reverse(events.begin(), events.end());
        priority_queue<array<int, 2>, vector<array<int, 2>>, greater<>> mn_pq;
        for (auto [x, type, i] : events) {
            if (type == +1) {
                mn_pq.push({ a[i][1], i });
            } else {
                next[i][0] = mn_pq.empty() ? -1 : mn_pq.top()[1];
            }
        }
        for (int t = 1; t < log; t++) {
            for (int i = 0; i < n; i++) {
                next[i][t] = next[i][t - 1] == -1 ? -1 : next[next[i][t - 1]][t - 1];
                prev[i][t] = prev[i][t - 1] == -1 ? -1 : prev[prev[i][t - 1]][t - 1];
            }
        }
        return make_pair(next, prev);
    }(n, a);

    auto forward_lift = [&](int i, int bound) {
        int lifted = 0;
        for (int t = next[i].size() - 1; t >= 0; t--) {
            int j = next[i][t];
            if (j != -1 && a[j][1] <= bound) {
                i = j;
                lifted += 1 << t;
            }
        }
        return lifted;
    };

    auto backward_lift = [&](int i, int bound) {
        int lifted = 0;
        for (int t = prev[i].size() - 1; t >= 0; t--) {
            int j = prev[i][t];
            if (j != -1 && bound <= a[j][0]) {
                i = j;
                lifted += 1 << t;
            }
        }
        return lifted;
    };

    set<array<int, 2>> cut = { {-INF, -1}, {INF, -1} };
    auto intersect = [&](int i, int j) {
        if (i == -1 || j == -1) return false;
        if (a[i] == a[j]) return false;
        return (a[j][0] < a[i][0] && a[i][0] < a[j][1]) || (a[i][0] < a[j][0] && a[j][0] < a[i][1]);
    };

    vector<int> key;
    int cur;
    for (int i = 0; i < n; i++) {
        auto [l, il] = *--cut.lower_bound(array<int, 2>{a[i][1], -INF});
        auto [r, ir] = *cut.upper_bound(array<int, 2>{a[i][0], +INF});
        if (intersect(i, il) || intersect(i, ir)) {
            continue;
        }
        int cur_try;
        if (il == -1 && ir == -1) {
            cur_try = forward_lift(i, INF) + backward_lift(i, -INF) + 1;
        } else if (il == -1) {
            cur_try = cur - backward_lift(ir, -INF) + forward_lift(i, r) + backward_lift(i, -INF) + 1;
        } else if (ir == -1) {
            cur_try = cur - forward_lift(il, INF) + forward_lift(i, INF) + backward_lift(i, l) + 1;
        } else {
            cur_try = cur - forward_lift(il, r) + forward_lift(i, r) + backward_lift(i, l) + 1;
        }
        if (cur_try < k) continue;
        cur = cur_try;
        key.push_back(i);
        cut.insert({a[i][0], i});
        cut.insert({a[i][1], i});
    }

    if (key.empty()) {
        cout << -1 << '\n';
    } else {
        assert(key.size() >= k);
        key.resize(k);
        for (int i : key) {
            cout << i + 1 << '\n';
        }
    }
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from event2.cpp:1:
event2.cpp: In function 'int main()':
event2.cpp:121:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  121 |         assert(key.size() >= k);
      |                ~~~~~~~~~~~^~~~
event2.cpp:109:27: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
  109 |             cur_try = cur - forward_lift(il, r) + forward_lift(i, r) + backward_lift(i, l) + 1;
      |                       ~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 187 ms 51276 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 1 ms 348 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 1 ms 348 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 187 ms 51276 KB Output isn't correct
5 Halted 0 ms 0 KB -