oj.uz

Submission #898462

# Submission time Handle Problem Language Result Execution time Memory
898462 2024-01-04T17:07:37 Z LucaIlie Event Hopping 2 (JOI21_event2) C++17
0 / 100
 3000 ms 3400 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 3028 ms 3400 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 3028 ms 3400 KB Time limit exceeded
5 Halted 0 ms 0 KB -