Submission #545609

#	Time	Username	Problem	Language	Result	Execution time	Memory
545609		chonka	Cake 3 (JOI19_cake3)	C++98	100 / 100	1133 ms	202348 KiB

cake3

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

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

#define MAXN 200007
const ll inf = 1e17 ;

int n , k ;
pair < int , int > a[ MAXN ] ;
pair < int , int > srt[ MAXN ] ;
int ord[ MAXN ] ;

struct node {
    ll sm ;
    int cnt ;
    node *pl , *pr ;
    node ( ) { sm = cnt = 0 ; pl = pr = NULL ; }
    node ( node *_pl , node *_pr ) {
        pl = _pl ; pr = _pr ;
        sm = 0 ; cnt = 0 ;
        if ( pl != NULL ) {
            sm += pl->sm ;
            cnt += pl->cnt ;
        }
        if ( pr != NULL ) {
            sm += pr->sm ;
            cnt += pr->cnt ;
        }
    }
};

node* root[ MAXN ] ;

node* init ( int l , int r ) {
    if ( l == r ) { return new node ( ) ; }
    int mid = ( l + r ) / 2 ;
    node *ret = new node ( init ( l , mid ) , init ( mid + 1 , r ) ) ;
    return ret ;
}

node* update ( node *w , int l , int r , int pos , int add ) {
    if ( l == r ) {
        node *ret = new node ( ) ;
        ++ ret->cnt ;
        ret->sm += add ;
        return ret ;
    }
    int mid = ( l + r ) / 2 ;
    if ( pos <= mid ) {
        return new node ( update ( w->pl , l , mid , pos , add ) , w->pr ) ;
    }
    else {
        return new node ( w->pl , update ( w->pr , mid + 1 , r , pos , add ) ) ;
    }
}

pair < ll , int > query ( node *st , node *en , int l , int r , int lft ) {
    if ( lft == 0 ) { return { 0 , 0 } ; }
    if ( en->cnt - st->cnt <= lft ) {
        return { en->sm - st->sm , en->cnt - st->cnt } ;
    }
    int mid = ( l + r ) / 2 ;
    pair < ll , int > ret1 = query ( st->pr , en->pr , mid + 1 , r , lft ) ;
    pair < ll , int > ret2 = query ( st->pl , en->pl , l , mid , lft - ret1.second ) ;
    return { ret1.first + ret2.first , ret1.second + ret2.second } ;
}

ll ans[ MAXN ] ;

ll calc ( int x , int y ) {
    if ( y - x - 1 < k - 2 ) { return -inf ; }
    ll ret = 2 * ( a[ x ].second - a[ y ].second ) ;
    ret += a[ x ].first + a[ y ].first ;
    pair < ll , int > hh = query ( root[ x ] , root[ y - 1 ] , 1 , n , k - 2 ) ;
    ret += hh.first ;
    return ret ;
}


void f ( int l , int r , int st , int en ) {
    if ( l > r ) { return ; }
    int mid = ( l + r ) / 2 ;
    int wh = -1 ;
    for ( int i = max ( mid + k - 1 , st ) ; i <= en ; ++ i ) {
        ll cand = calc ( mid , i ) ;
        if ( ans[ mid ] <= cand ) {
            ans[ mid ] = cand ;
            wh = i ;
        }
    }
    if ( l < mid ) {
        f ( l , mid - 1 , st , wh ) ;
    }
    if ( mid < r ) {
        f ( mid + 1 , r , wh , en ) ;
    }
}

void input ( ) {
    cin >> n >> k ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ].first >> a[ i ].second ;
    }
    auto cmp = [ & ] ( pair < int , int > p1 , pair < int , int > p2 ) {
        if ( p1.second != p2.second ) { return ( p1.second < p2.second ) ; }
        return p1.first < p2.first ;
    };
    sort ( a + 1 , a + n + 1 , cmp ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        srt[ i ] = { a[ i ].first , i } ;
    }
    sort ( srt + 1 , srt + n + 1 ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        ord[ srt[ i ].second ] = i ;
    }
}

void solve ( ) {
    root[ 0 ] = init ( 1 , n ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        root[ i ] = update ( root[ i - 1 ] , 1 , n , ord[ i ] , a[ i ].first ) ;
    }
    for ( int i = 1 ; i <= n - k + 1 ; ++ i ) {
        ans[ i ] = -inf ;
    }
    f ( 1 , n - k + 1 , 1 , n ) ;
    ll ret = -inf ;
    for ( int i = 1 ; i <= n - k + 1 ; ++ i ) {
        ret = max ( ret , ans[ i ] ) ;
    }
    cout << ret << "\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: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76