Submission #541283

#	Time	Username	Problem	Language	Result	Execution time	Memory
541283		chonka	Event Hopping 2 (JOI21_event2)	C++98	0 / 100	187 ms	38020 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 20

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 ] ;
    }
}

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 ] ] ;
            }
        }
    }
    s.clear ( ) ;
    s.insert ( 1 ) ;
    s.insert ( mx_coord + 1 ) ;
    int aux = f ( 1 , mx_coord + 1 ) ;
    if ( aux < k ) {
        cout << "-1\n" ;
        return ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        auto it = s.upper_bound ( a[ i ].first ) ;
        if ( it != s.end ( ) && *it < a[ i ].second ) { continue ; }
        int en = (*it) ;
        -- it ;
        int st = (*it) ;
        int hh = aux ;
        hh -= f ( st , en ) ;
        hh += f ( st , a[ i ].first ) + f ( a[ i ].second , en ) + 1 ;
        if ( hh >= k ) {
            ans.push_back ( i ) ;
            s.insert ( a[ i ].first ) ;
            s.insert ( a[ i ].second ) ;
            aux = hh ;
        }
        if ( ans.size ( ) == 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 ;
}

Compilation message (stderr)

event2.cpp: In function 'void solve()':
event2.cpp:87:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   87 |         if ( ans.size ( ) == k ) { break ; }
      |              ~~~~~~~~~~~~~^~~~

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