oj.uz

Submission #673891

# Submission time Handle Problem Language Result Execution time Memory
673891 2022-12-22T10:59:48 Z mdn2002 Holiday (IOI14_holiday) C++14
100 / 100
 613 ms 10152 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 724 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 0 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 9308 KB Output is correct
2 Correct 173 ms 9656 KB Output is correct
3 Correct 161 ms 9440 KB Output is correct
4 Correct 159 ms 9436 KB Output is correct
5 Correct 177 ms 9288 KB Output is correct
6 Correct 46 ms 3024 KB Output is correct
7 Correct 91 ms 5136 KB Output is correct
8 Correct 111 ms 5644 KB Output is correct
9 Correct 30 ms 2896 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 980 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 6 ms 1012 KB Output is correct
5 Correct 8 ms 980 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 9304 KB Output is correct
2 Correct 156 ms 10108 KB Output is correct
3 Correct 220 ms 5324 KB Output is correct
4 Correct 7 ms 980 KB Output is correct
5 Correct 2 ms 704 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 613 ms 10152 KB Output is correct
9 Correct 480 ms 10040 KB Output is correct