제출 #1118491

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118491		Zero_OP	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	142 ms	24056 KiB

event2

#include <bits/stdc++.h>

using namespace std;

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
bool minimize(T& a, const T& b){
    if(a > b) return a = b, true;
    return false;
}

template<typename T>
bool maximize(T& a, const T& b){
    if(a < b) return a = b, true;
    return false;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N, K;
    cin >> N >> K;

    vector<int> l(N), r(N), v;
    for(int i = 0; i < N; ++i){
        cin >> l[i] >> r[i];
        v.emplace_back(l[i]);
        v.emplace_back(r[i]);
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    int bound = (int)v.size();
    vector<int> up(bound + 1, bound + 1);
    for(int i = 0; i < N; ++i){
        l[i] = lower_bound(v.begin(), v.end(), l[i]) - v.begin() + 1;
        r[i] = lower_bound(v.begin(), v.end(), r[i]) - v.begin() + 1;
        minimize(up[l[i]], r[i]);
    }

    for(int i = bound - 1; i >= 1; --i){
        minimize(up[i], up[i + 1]);
    }

    int L = 32 - __builtin_clz(bound);
    vector<vector<int>> next(L, vector<int>(bound + 1, bound + 1));
    next[0] = up;
    for(int i = 1; i < L; ++i){
        for(int j = 1; j <= bound; ++j){
            if(next[i - 1][j] == bound + 1) next[i][j] = bound + 1;
            else next[i][j] = next[i - 1][next[i - 1][j]];
        }
    }

    auto count_max = [&](int l, int r) -> int{
        if(l > r) return 0;
        int ans = 0;
        for(int i = L - 1; i >= 0; --i){
            if(next[i][l] <= r){
                ans += (1 << i);
                l = next[i][l];
            }
        }
        return ans;
    };

    vector<int> ans;

    int cur = count_max(1, bound);
    if(cur < K){
        cout << -1 << '\n';
        return 0;
    }

    set<pair<int, int>> online;

    online.insert({1, 1});
    online.insert({bound, bound});

    int need = K;
    for(int i = 0; i < N && need > 0; ++i){
        auto ite = online.lower_bound({r[i], -1e9});
        int boundL = prev(ite) -> second, boundR = ite -> first;
        if(l[i] < boundL) continue;
        int delta = -count_max(boundL, boundR) + count_max(boundL, l[i]) + count_max(r[i], boundR) + 1;
        if(delta + cur >= K){
            --need;
            ans.emplace_back(i);
            cur += delta;
            online.insert({l[i], r[i]});
        }
    }

    assert((int)ans.size() == K);
    for(auto it : ans) cout << it + 1 << '\n';

    return 0;
}

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