Submission #1118310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118310		Zero_OP	Event Hopping 2 (JOI21_event2)	C++14	0 / 100	51 ms	11048 KiB

event2

#include <bits/stdc++.h>

using namespace std;

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

struct max_suffix_fenwick{
    vector<int> bit;
    max_suffix_fenwick(int n) : bit(n + 1, 0) {}

    void update(int i, int v){
        for(; i > 0; i -= i & (-i)) bit[i] = max(bit[i], v);
    }

    int query(int i){
        int best = 0;
        for(; i < (int)bit.size(); i += i & (-i)) best = max(best, bit[i]);
        return best;
    }
};

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);
    vector<int> 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());

    vector<tuple<int, int, int>> vt;
    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;
        vt.emplace_back(L[i], R[i], i);
    }

    sort(vt.begin(), vt.end());

    int bound = (int)v.size();
    max_suffix_fenwick ft(bound);

    vector<int> dp(N);
    vector<vector<int>> groups(N + 1);
    for(int t = N - 1; t >= 0; --t){
        int l, r, i;
        tie(l, r, i) = vt[t];
        dp[i] = ft.query(r) + 1;
        ft.update(l, dp[i]);
        groups[dp[i]].emplace_back(i);
    }

    vector<int> ans;
    for(int i = 1; i <= N; ++i) if(!groups[i].empty()){
        ans.emplace_back(*min_element(groups[i].begin(), groups[i].end()));
    }

    if((int)ans.size() < K){
        cout << -1 << '\n';
    } else{
        sort(ans.begin(), ans.end());
        ans.resize(K);
        for(auto it : ans) cout << it + 1 << '\n';
    }

    return 0;
}

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