제출 #673891

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
673891		mdn2002	휴가 (IOI14_holiday)	C++14	100 / 100	613 ms	10152 KiB

holiday

#include<bits/stdc++.h>
#include"holiday.h"

using namespace std;
long long N , Start , D , a [100005] , ind [100005] , tree [400005][3] , k , ll = 1 , rr = 1 , ans;
vector < pair < int , int > > v;
int aa [100005];

void up ( int nod , int l , int r , int x , long long val , int ad )
{
    if ( x < l || r < x ) return;
    if ( l == r )
    {
        tree [nod][0] += val;
        tree [nod][1] += ad;
        return;
    }
    int mid = ( l + r ) / 2;
    up ( nod * 2 , l , mid , x , val , ad );
    up ( nod * 2 + 1 , mid + 1 , r , x , val , ad );
    tree [nod][0] = tree [ nod * 2 ][0] + tree [ nod * 2 + 1 ][0];
    tree [nod][1] = tree [ nod * 2 ][1] + tree [ nod * 2 + 1 ][1];
}
long long qr ( int nod , int l , int r , int d )
{
    if ( d == 0 ) return 0;
    if ( l == r ) return tree [nod][0];
    int mid = ( l + r ) / 2;
    if ( tree [ nod * 2 + 1 ][1] <= d ) return tree [ nod * 2 + 1 ][0] + qr ( nod * 2 , l , mid , d - tree [ nod * 2 + 1 ][1] );
    else return qr ( nod * 2 + 1 , mid + 1 , r , d );
}
void c ( int x , int y )
{
    while ( ll < x )
    {
        up ( 1 , 1 , N , ind [ll] , - a [ll] , -1 );
        ll ++;
    }
    while ( ll > x )
    {
        ll --;
        up ( 1 , 1 , N , ind [ll] , a [ll] , 1 );
    }
    while ( rr < y )
    {
        rr ++;
        up ( 1 , 1 , N , ind [rr] , a [rr] , 1 );

    }
    while ( rr > y )
    {
        up ( 1 , 1 , N , ind [rr] , - a [rr] , -1 );
        rr --;
    }
}

void f ( int l , int r , int x , int y )
{
    if ( l > r ) return;
    int mid = ( l + r ) / 2 , opt = y;
    long long mx = 0;
    for ( int i = min ( y , mid ) ; i >= x ; i -- )
    {
        c ( i , mid );
        long long dd = D - ( mid - i + min ( mid - Start , Start - i ) ) , val = qr ( 1 , 1 , N , dd );
        if ( mx < val )
        {
            mx = val;
            opt = i;
        }
    }
    ans = max ( ans , mx );
    f ( l , mid - 1 , x , opt );
    f ( mid + 1 , r , opt , y );
}


long long int findMaxAttraction ( int n , int start , int d , int attraction [] )
{
    N = n , Start = start , D = d;
    Start ++;
    for ( int i = 1 ; i <= N ; i ++ )
    {
        a [i] = attraction [ i - 1 ];
        v . push_back ( { a [i] , i } );
    }

    sort ( v . begin () , v . end () );
    for ( auto x : v ) ind [ x . second ] = ++ k;

    up ( 1 , 1 , N , ind [1] , a [1] , 1 );

    f ( Start , N , 1 , Start );

    return ans;
}

/*
int main()
{
    cin >> N >> Start >> D;
    for ( int i = 0 ; i < N ; i ++ ) cin >> aa [i];

    cout << findMaxAttraction ( N , Start , D , aa );
}
*/

/*
5 2 7
10 2 20 30 1
*/

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53