Submission #541285

#	Time	Username	Problem	Language	Result	Execution time	Memory
541285		chonka	Event Hopping 2 (JOI21_event2)	C++98	100 / 100	315 ms	45572 KiB

event2

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

// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define MAXN 200007
#define LOG 18

int n , k , mx_coord ;
pair < int , int > a[ MAXN ] ;
vector < int > ans ;

set < int > s ;
map < int , int > w ;

int nxt[ LOG ][ MAXN ] ;

int f ( int st , int en ) {
    int ans = 0 ;
    for ( int i = LOG - 1 ; i >= 0 ; -- i ) {
        if ( nxt[ i ][ st ] <= en ) {
            ans += ( 1 << i ) ;
            st = nxt[ i ][ st ] ;
        }
    }
    return ans ;
}

void input ( ) {
    cin >> n >> k ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ].first >> a[ i ].second ;
        s.insert ( a[ i ].first ) ;
        s.insert ( a[ i ].second ) ;
    }
    for ( auto val : s ) {
        w[ val ] = ++ mx_coord ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        a[ i ].first = w[ a[ i ].first ] ;
        a[ i ].second = w[ a[ i ].second ] ;
    }
}

set < pair < int , int > > act ;

void solve ( ) {
    for ( int i = 0 ; i < LOG ; ++ i ) {
        for ( int j = 1 ; j <= mx_coord ; ++ j ) {
            nxt[ i ][ j ] = MAXN ; 
        }
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        nxt[ 0 ][ a[ i ].first ] = min ( nxt[ 0 ][ a[ i ].first ] , a[ i ].second ) ;
    }
    for ( int i = mx_coord - 1 ; i >= 1 ; -- i ) {
        nxt[ 0 ][ i ] = min ( nxt[ 0 ][ i ] , nxt[ 0 ][ i + 1 ] ) ;
    }
    for ( int i = 1 ; i < LOG ; ++ i ) {
        for ( int j = 1 ; j <= mx_coord ; ++ j ) {
            if ( nxt[ i - 1 ][ j ] <= mx_coord ) {
                nxt[ i ][ j ] = nxt[ i - 1 ][ nxt[ i - 1 ][ j ] ] ;
            }
        }
    }
    act.insert ( { 1 , -1 } ) ;
    act.insert ( { mx_coord + 1 , 1 } ) ;
    int aux = f ( 1 , mx_coord + 1 ) ;
    if ( aux < k ) {
        cout << "-1\n" ;
        return ;
    }
    int cnt = 0 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        auto it = act.upper_bound ( { a[ i ].first , MAXN } ) ;
        if ( it->first < a[ i ].second || it->second == -1 ) { continue ; }
        int en = it->first ;
        -- it ;
        int st = it->first;
        int hh = aux ;
        hh -= f ( st , en ) ;
        hh += f ( st , a[ i ].first ) + f ( a[ i ].second , en ) + 1 ;
        if ( hh >= k ) {
            ++ cnt ;
            ans.push_back ( i ) ;
            act.insert ( { a[ i ].first , 1 } ) ;
            act.insert ( { a[ i ].second , -1 } ) ;
            aux = hh ;
        }
        if ( cnt == k ) { break ; }
    }
    for ( auto x : ans ) {
        cout << x << "\n" ;
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ;
    // cin >> t ;
    while ( t -- ) {
        input ( ) ;
        solve ( ) ;
    }
    return 0 ;
}

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