Submission #236979

#	Time	Username	Problem	Language	Result	Execution time	Memory
236979		DodgeBallMan	Cake 3 (JOI19_cake3)	C++14	0 / 100	5 ms	384 KiB

cake3

#include <bits/stdc++.h>
#define pii pair<long long, long long>
#define x first
#define y second 

using namespace std;

const int N = 2e5 + 10;

int n, m, ver[N];
pii cake[N];
vector<long long> t, coord;
vector<int> sz, L, R;
long long ans[N], ret;

int newleaf( long long va, int ss ) {
    t.emplace_back( va ), sz.emplace_back( ss ), L.emplace_back( -1 ), R.emplace_back( -1 );
    return (int)t.size() - 1;
}

int newpar( int l, int r ) {
    t.emplace_back( t[l] + t[r] ), sz.emplace_back( sz[l] + sz[r] );
    L.emplace_back( l ), R.emplace_back( r );
    return (int)t.size() - 1;
}

int get( int x ) { return lower_bound( coord.begin(), coord.end(), x ) - coord.begin() + 1; }

int build( int l = 1, int r = coord.size() ) {
    if( l == r ) return newleaf( 0, 0 );
    int mid = l + r >> 1;
    return newpar( build( l, mid ), build( mid+1, r ) );
}

int update( int x, long long va, int p, int l = 1, int r = coord.size() ) {
    if( l == r ) return newleaf( t[p] + va, sz[p] + 1 );
    int mid = l + r >> 1;
    if( mid >= x ) return newpar( update( x, va, L[p], l, mid ), R[p] );
    else return newpar( L[p], update( x, va, R[p], mid+1, r ) );
}

long long query( int a, int b, int x, int l = 1, int r = coord.size() ) {
    if( x == 0 ) return 0LL;
    if( l == r ) return t[b] - t[a];
    int mid = l + r >> 1;
    if( sz[R[b]] - sz[R[a]] >= x ) return query( R[a], R[b], x, mid+1, r );
    else return t[R[b]] - t[R[a]] + query( L[a], L[b], x, l, mid );
}

void solve( int l, int r, int optl, int optr ) {
    if( l > r ) return ;
    int mid = l + r >> 1, idx;
    ans[mid] = -1e18;
    for( int i = max( mid + m - 1, optl ) ; i <= optr ; i++ ) {
        int now = query( ver[mid], ver[i-1], m-2 ) + cake[i].x + cake[mid].x - 2*cake[i].y + 2*cake[mid].y;
        //printf("%d %d\n",i,now);
        if( now > ans[mid] ) ans[mid] = now, idx = i;
    }
    //printf("%d %d %d %d %d %lld\n",l,mid,r,optl,optr,ans[mid]);
    solve( l, mid-1, optl, idx ), solve( mid+1, r, idx, optr );
}

int main()
{
    t.emplace_back( 0 ), sz.emplace_back( 0 ), R.emplace_back( 0 ), L.emplace_back( 0 );
    scanf("%d %d",&n,&m);
    for( int i = 1 ; i <= n ; i++ ) {
        scanf("%lld %lld",&cake[i].x,&cake[i].y);
        coord.emplace_back( cake[i].x );
    }
    sort( cake + 1, cake + 1 + n, [&]( const pii &a, const pii &b ) {
        return a.y < b.y;
    });
    sort( coord.begin(), coord.end() );
    coord.resize( unique( coord.begin(), coord.end() ) - coord.begin() );
    ver[0] = build();
    for( int i = 1 ; i <= n ; i++ ) ver[i] = update( get( cake[i].x ), cake[i].x, ver[i-1] );
    solve( 1, n-m+1, 1, n );
    for( int i = 1 ; i <= n-m+1 ; i++ ) ret = max( ret, ans[i] );
    printf("%lld",ret);
    return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'int build(int, int)':
cake3.cpp:31:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
cake3.cpp: In function 'int update(int, long long int, int, int, int)':
cake3.cpp:37:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
cake3.cpp: In function 'long long int query(int, int, int, int, int)':
cake3.cpp:45:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
cake3.cpp: In function 'void solve(int, int, int, int)':
cake3.cpp:52:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1, idx;
               ~~^~~
cake3.cpp: In function 'int main()':
cake3.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~
cake3.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld",&cake[i].x,&cake[i].y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp: In function 'void solve(int, int, int, int)':
cake3.cpp:60:10: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
     solve( l, mid-1, optl, idx ), solve( mid+1, r, idx, optr );
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 19
• Subtask 3: 0 / 76