Submission #898515

#	Time	Username	Problem	Language	Result	Execution time	Memory
898515		LucaIlie	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	1035 ms	32492 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_M = 2 * MAX_N;
int bucket[MAX_M + 2], leftBucket[MAX_M + 1], rightBucket[MAX_M + 1], maxEvents[MAX_M + 1], eventRightEnd[MAX_M + 1], minR[MAX_M + 2];
event events[MAX_N + 1];
set<int> rightEnds[MAX_M + 1];
set<event> selectedEvents;
map<int, int> normal;

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

void calcBucket( int b ) {
    for ( int i = rightBucket[b]; i >= leftBucket[b]; i-- ) {
        maxEvents[i] = 0;
        eventRightEnd[i] = i;
        if ( bucket[i + 1] == b ) {
            if ( maxEvents[i + 1] > maxEvents[i] ) {
                maxEvents[i] = maxEvents[i + 1];
                eventRightEnd[i] = eventRightEnd[i + 1];
            }
        }
        if ( !rightEnds[i].empty() && bucket[*rightEnds[i].begin()] == b ) {
            if ( maxEvents[*rightEnds[i].begin()] + 1 > maxEvents[i] ) {
                maxEvents[i] = maxEvents[*rightEnds[i].begin()] + 1;
                eventRightEnd[i] = eventRightEnd[*rightEnds[i].begin()];
            } else if ( maxEvents[*rightEnds[i].begin()] + 1 == maxEvents[i] )
                eventRightEnd[i] = min( eventRightEnd[i], eventRightEnd[*rightEnds[i].begin()] );
        }
    }
}

int query( int l, int r ) {
    int nrEvents = 0;
    while ( eventRightEnd[l] <= r ) {
        nrEvents += maxEvents[l];
        l = eventRightEnd[l];
        nrEvents++;
        l = minR[l];
    }
    while ( l <= r ) {
        nrEvents++;
        l = minR[l];
    }

    return nrEvents - 1;
}

int main() {
    int n, k;

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

    int m = 0;
    for ( auto p: normal )
        normal[p.first] = ++m;
    for ( int i = 1; i <= n; i++ ) {
        events[i].l = normal[events[i].l];
        events[i].r = normal[events[i].r];
        rightEnds[events[i].l].insert( events[i].r );
    }

    minR[m + 1] = m + 1;
    for ( int i = m; i >= 1; i-- )
        minR[i] = min( minR[i + 1], (!rightEnds[i].empty() ? *rightEnds[i].begin() : m + 1) );

    int bucketSize = sqrt( m ), nrBuckets = 0;
    for ( int i = 1; i <= m; i += bucketSize )  {
        nrBuckets++;
        leftBucket[nrBuckets] = i;
        rightBucket[nrBuckets] = min( i + bucketSize - 1, m );
        for ( int j = i; j < i + bucketSize && j <= m; j++ )
            bucket[j] = nrBuckets;
        calcBucket( nrBuckets );
    }
    eventRightEnd[m + 1] = m + 1;

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

        auto p = selectedEvents.lower_bound( events[i] );
        int r = p->l;
        p--;
        int l = p->r;

        int copyNrEvents = nrEvents;
        nrEvents -= query( l, r );
        rightEnds[events[i].l].erase( events[i].r );
        calcBucket( bucket[events[i].l] );
        nrEvents += query( l, events[i].l ) + query( events[i].r, r );

        if ( nrEvents >= k - 1 ) {
            selectedEvents.insert( events[i] );
            ans.push_back( i );
            k--;
        } else
            nrEvents = copyNrEvents;
    }

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

    return 0;
}

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