Submission #1118480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118480		Zero_OP	Event Hopping 2 (JOI21_event2)	C++14	1 / 100	29 ms	2656 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.ans", "w", stdout);
#endif // LOCAL

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

    struct event{
        int l, r, id;
        event(int l, int r, int id) : l(l), r(r), id(id) {}
        bool operator < (const event& o){
            if(l != o.l) return l < o.l;
            if(r != o.r) return r < o.r;
            return id < o.id;
        }
    };

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

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

    for(int i = 0; i < N; ++i){
        events[i].l = lower_bound(v.begin(), v.end(), events[i].l) - v.begin();
        events[i].r = lower_bound(v.begin(), v.end(), events[i].r) - v.begin();
    }

    vector<int> ans;

    for(int mask = (1 << K) - 1; mask < (1 << N); ++mask) if(__builtin_popcount(mask) == K){
        vector<int> diff((int)v.size());
        for(int i = 0; i < N; ++i){
            if(mask >> i & 1){
                ++diff[events[i].l];
                --diff[events[i].r];
            }
        }

        bool ok = true;
        for(int i = 0; i < (int)v.size(); ++i){
            diff[i] += (i == 0 ? 0 : diff[i - 1]);
            if(diff[i] > 1){
                ok = false;
            }
        }

        if(ok){
            vector<int> cur;
            for(int i = 0; i < N; ++i){
                if(mask >> i & 1){
                    cur.emplace_back(i);
                }
            }

            if(ans.empty() || ans > cur) ans = cur;
        }
    }

    if(ans.empty()) cout << -1 << '\n';
    else{
        for(auto x : ans) cout << x + 1 << '\n';
    }

    return 0;
}

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