제출 #1229400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1229400		__moin__	Event Hopping 2 (JOI21_event2)	C++20	32 / 100	3089 ms	12780 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);
        reverse(events.begin(), events.end());
        curmax = 0;
        for (auto [inter, type] : events) {
            if (type == END) {
                dpright[inter.idx] = curmax + 1;
            } else {
                curmax = max(curmax, dpright[inter.idx]);
            }
        }

        // 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: 0 / 7
• Subtask 2: 1 / 1
• Subtask 3: 31 / 31
• Subtask 4: 0 / 61