Submission #641527

#	Time	Username	Problem	Language	Result	Execution time	Memory
641527		skittles1412	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	139 ms	23584 KiB

event2

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

constexpr int maxn = 2e5 + 5, logn = 18;

int lift[logn][maxn];

int ccomp(vector<int*>&& arr) {
    sort(begin(arr), end(arr), [&](const int* a, const int* b) -> bool {
        return *a < *b;
    });
    int j = 0;
    for (int i = 0, prv; i < sz(arr); i++) {
        j += i && prv != *arr[i];
        prv = *arr[i];
        *arr[i] = j;
    }
    return j + 1;
}

void solve() {
    int n, kv;
    cin >> n >> kv;
    int arr[n][2];
    for (auto& [l, r] : arr) {
        cin >> l >> r;
    }
    vector<int*> comp;
    for (auto& [l, r] : arr) {
        comp.emplace_back(&l);
        comp.emplace_back(&r);
    }
    int m = ccomp(std::move(comp));
    fill(lift[0], lift[0] + m + 1, m);
    for (auto& [x, y] : arr) {
        lift[0][x] = min(lift[0][x], y);
    }
    for (int i = m - 1; i >= 0; i--) {
        lift[0][i] = min(lift[0][i], lift[0][i + 1]);
    }
    for (int i = 1; i < logn; i++) {
        for (int j = 0; j <= m; j++) {
            lift[i][j] = lift[i - 1][lift[i - 1][j]];
        }
    }
    auto query = [&](int l, int r) -> int {
        int ans = 0;
        for (int i = logn - 1; i >= 0; i--) {
            if (lift[i][l] <= r) {
                ans |= 1 << i;
                l = lift[i][l];
            }
        }
        return ans;
    };
    int cans = query(0, m - 1);
    if (cans < kv) {
        cout << -1 << endl;
        return;
    }
    set<pair<int, int>> segs;
    segs.emplace(-1, 0);
    segs.emplace(m - 1, m);
    for (int i = 0; i < n && sz(segs) - 2 < kv; i++) {
        auto& [l, r] = arr[i];
        auto it = segs.lower_bound({l, r});
        int qr = it->first, ql = (--it)->second;
        if (ql <= l && r <= qr) {
            int nans = cans - query(ql, qr) + query(ql, l) + query(r, qr);
            if (nans + sz(segs) - 1 >= kv) {
                cans = nans;
                segs.emplace(l, r);
                cout << i + 1 << endl;
            }
        }
    }
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cin.exceptions(ios::failbit);
    solve();
}

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