This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |