Submission #673891

#TimeUsernameProblemLanguageResultExecution timeMemory
673891mdn2002Holiday (IOI14_holiday)C++14
100 / 100
613 ms10152 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...