Submission #898462

#	Time	Username	Problem	Language	Result	Execution time	Memory
898462		LucaIlie	Event Hopping 2 (JOI21_event2)	C++17	0 / 100	3028 ms	3400 KiB

event2

#include <bits/stdc++.h>

using namespace std;

struct event {
    int l, r;

    bool operator < ( const event e ) const {
        if ( l == e.l )
            return r < e.r;
        return l < e.l;
    }
};

const int MAX_N = 1e5;
const int MAX_VAL = 1e9 + 1;
event events[MAX_N + 1];
set<event> selectedEvents;

bool check ( event e ) {
    auto p = selectedEvents.lower_bound( e );
    if ( e.r <= p->l && (--p)->r <= e.l )
        return true;
    return false;
}

int main() {
    int n, k;

    cin >> n >> k;
    for ( int i = 1; i <= n; i++ )
        cin >> events[i].l >> events[i].r;

    selectedEvents.insert( { 0, 0 } );
    selectedEvents.insert( { MAX_VAL, MAX_VAL } );
    vector<int> ans;
    for ( int i = 1; i <= n && k > 0; i++ ) {
        if ( !check( events[i] ) )
            continue;

        vector<event> queryEvents;
        for ( int j = i + 1; j <= n; j++ ) {
            if ( check( events[j] ) )
                queryEvents.push_back( events[j] );
        }
        sort( queryEvents.begin(), queryEvents.end(), []( event a, event b ) {
            if ( a.r == b.r )
                return a.l < b.l;
            return a.r < b.r;
        } );

        int x = 0, t = 0;
        for ( event e: events ) {
            if ( e.l >= t ) {
                x++;
                t = e.r;
            }
        }
        if ( x >= k - 1 ) {
            ans.push_back( i );
            selectedEvents.insert( events[i] );
            k--;
        }
    }

    if ( k > 0 ) {
        cout << -1;
        return 0;
    }
    for ( int i: ans )
        cout << i << "\n";

    return 0;
}

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