Submission #1229451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229451		__moin__	Event Hopping 2 (JOI21_event2)	C++20	7 / 100	30 ms	6348 KiB

event2

#include <bits/stdc++.h>
using namespace std;

#define BEGIN 0
#define END 1
int TYPE = BEGIN;

struct interval {
    int s, t, idx;
    bool operator<(interval o) {
        if (TYPE == BEGIN) return s < o.s;
        else return t < o.t;
    }
    bool overlaps(interval o) {
        // intersection [max(s, o.s); min(t, o.t)]
        return max(s, o.s) < min(t, o.t);
    }
};

struct event {
    interval inter;
    int type;
    bool operator<(event o) {
        int time = (type == BEGIN ? inter.s : inter.t);
        int otime = (o.type == BEGIN ? o.inter.s : o.inter.t);
        if (time == otime) {
            return type == END && o.type != END;
        }
        return time < otime;
    }
};

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

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

    vector<interval> intervals(n);
    for (auto& e : intervals) cin >> e.s >> e.t;
    for (int i = 0; i < n; i++) intervals[i].idx = i;
    // intervals.push_back({-1, -1, -1});
    // intervals.push_back({(int)1e9+1, (int)1e9+1, -1});
    vector<event> events(2*n);
    for (int i = 0; i < n; i++) {
        events[2*i] = {intervals[i], BEGIN};
        events[2*i+1] = {intervals[i], END};
    }

    // vector<bool> included(n, 1);

    // for (int i = 0, K = k; i < K; i++) {
        // find optimal value
        vector<int> dpleft(n);
        sort(events.begin(), events.end());
        int curmax = 0;
        for (auto [inter, type] : events) {
            if (type == BEGIN) {
                dpleft[inter.idx] = curmax + 1;
            } else {
                curmax = max(curmax, dpleft[inter.idx]);
            }
        }

        vector<int> dpright(n);
        // vector<int> next(n);
        reverse(events.begin(), events.end());
        curmax = 0;
        int curnext = 1;
        for (auto [inter, type] : events) {
            if (type == END) {
                dpright[inter.idx] = curmax + 1;
                // next[inter.idx] = -curnext;
            } else {
                curmax = max(curmax, dpright[inter.idx]);
            }
        }

        vector<int> ans;
        int pointer = 0;
        for (int i = 0; i < k; i++) {
            while (dpright[pointer] < k-i)
                if(++pointer >= n)
                    goto fail;
            ans.push_back(pointer); // take pointer
            int best = pointer;
            if (i == k-1) break;
            while (intervals[pointer].s < intervals[best].t)
                if(++pointer >= n)
                    goto fail;
        }
        for (int e : ans) cout << e+1 << "\n";
        exit(0);

        fail:
        cout << "-1\n";
        exit(0);

        // find first possible
        // for (int best = 0; best < n; best++) {
        //     if (!included[best]) continue;
        //     if (dpleft[best] + dpright[best] - 1 >= k) {
        //         cout << best+1 << "\n";
        //         included[best] = 0;
        //         for (int j = 0; j < n; j++) {
        //             if (intervals[best].overlaps(intervals[j]))
        //                 included[j] = 0;
        //         }
        //         k--;
        //         goto skip;
        //     }
        //     included[best] = 0;
        // }
        // cout << "-1\n";
        // return 0;
        // skip:
        // vector<event> newevents;
        // for (event e : events) {
        //     if (included[e.inter.idx]) newevents.push_back(e);
        // }
        // events = newevents;
    // }

    return 0;
}

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