| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 784992 | lollipop | Holiday (IOI14_holiday) | C++17 | 0 ms | 0 KiB |
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 "holiday.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod = 1000000007 ;
const int mod1 = 998244353 ;
const int N = 2e5 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 , hs ;
int pos[ N ] , A[ N ] ;
pair < ll , int > dpl[ 2 ][ N ] , dpr[ 2 ][ N ] ;
//int lf[ N ] ;
pair < int , ll > node[ 4 * N ] ;
// pos -- realurs + 1 iyos xolme
void update( int v , int vl , int vr , int pos , int tp ){
if( vl == vr ){
if( tp == -1 ){
node[ v ] = { 0 , 0 } ;
return ;
}
else{
node[ v ] = { 1 , A[ pos ] } ;
return ;
}
}
int vm = ( vl + vr ) / 2 ;
if( vm >= pos ) update( v + v , vl , vm , pos , tp ) ;
else update( v + v + 1 , vm + 1 , vr , pos , tp ) ;
node[ v ].f = node[ v + v ].f + node[ v + v + 1 ].f ;
node[ v ].s = node[ v + v ].s + node[ v + v + 1 ].s ;
return ;
}
ll get( int v , int vl , int vr , int m ){
if( node[ v ].f <= m ) return node[ v ].s ;
int vm = ( vl + vr ) / 2 ;
if( node[ v + v + 1 ].f >= m ) return get( v + v + 1 , vm + 1 , vr , m ) ;
ll sm = node[ v + v + 1 ].s ;
m = m - node[ v + v + 1 ].f ;
sm = sm + get( v + v , vl , vm , m ) ;
return sm ;
}
int nn ;
void compr( int l , int r , int mn , int mx , int d , int start ){
if( l > r ) return ;
int mid = ( l + r ) / 2 ;
pair < ll , int > mm = { -1 , -1 } ;
for( int j = mn ; j <= mx ; j ++ ){
update( 1 , 1 , nn , pos[ j ] , 1 ) ;
int m = mid - ( j - start ) ;
if( m < 0 ) continue ;
ll cur = get( 1 , 1 , nn , m ) ;
if( cur > mm.f ){
mm = { cur , j } ;
}
}
dpr[ 0 ][ mid ] = { mm.f , mm.s } ;
for( int j = mx ; j > mm.s ; j -- )
update( 1 , 1 , nn , pos[ j ] , -1 ) ;
compr( mid + 1 , r , mm.s , mx , d , start ) ;
for( int j = mx ; j >= mn ; j -- )
update( 1 , 1 , nn , pos[ j ] , -1 ) ;
compr( l , mid - 1 , mn , mm.s , d , start ) ;
}
void coml( int l , int r , int mn , int mx , int d , int start ){
if( l > r ) return ;
int mid = ( l + r ) / 2 ;
pair < ll , int > mm = { 0 , -1 } ;
for( int j = mx ; j >= mn ; j -- ){
update( 1 , 1 , nn , pos[ j ] , 1 ) ;
int m = mid - ( start - j ) ;
if( m < 0 ) continue ;
ll cur = get( 1 , 1 , nn , m ) ;
if( cur > mm.f ){
mm = { cur , j } ;
}
}
dpl[ 1 ][ mid ] = { mm.f , mm.s } ;
for( int j = mn ; j < mm.s ; j ++ )
update( 1 , 1 , nn , pos[ j ] , -1 ) ;
coml( mid + 1 , r , mn , mm.s , d , start ) ;
for( int j = mn ; j <= mx ; j ++ )
update( 1 , 1 , nn , pos[ j ] , -1 ) ;
coml( l , mid - 1 , mm.s , mx , d , start ) ;
}
void compr1( int l , int r , int mn , int mx , int d , int start ){
if( l > r ) return ;
int mid = ( l + r ) / 2 ;
pair < ll , int > mm = { -1 , -1 } ;
for( int j = mn ; j <= mx ; j ++ ){
update( 1 , 1 , nn , pos[ j ] , 1 ) ;
int m = mid - ( j - start ) ;
if( m < 0 ) continue ;
ll cur = get( 1 , 1 , nn , m ) ;
if( cur > mm.f ){
mm = { cur , j } ;
}
}
dpr[ 1 ][ mid ] = { mm.f , mm.s } ;
for( int j = mx ; j > mm.s ; j -- )
update( 1 , 1 , nn , pos[ j ] , -1 ) ;
compr1( mid + 1 , r , mm.s , mx , d , start ) ;
for( int j = mx ; j >= mn ; j -- )
update( 1 , 1 , nn , pos[ j ] , -1 ) ;
compr1( l , mid - 1 , mn , mm.s , d , start ) ;
}
void coml1( int l , int r , int mn , int mx , int d , int start ){
if( l > r ) return ;
int mid = ( l + r ) / 2 ;
// cout << l << " " << r << " " << mid << endl ;
pair < ll , int > mm = { 0 , start } ;
for( int j = mx ; j >= mn ; j -- ){
update( 1 , 1 , nn , pos[ j ] , 1 ) ;
int m = mid - ( start - j ) ;
if( m < 0 ) continue ;
ll cur = get( 1 , 1 , nn , m ) ;
if( cur > mm.f ){
mm = { cur , j } ;
}
}
dpl[ 0 ][ mid ] = { mm.f , mm.s } ;
//cout << mid << endl ;
for( int j = mn ; j < mm.s ; j ++ )
update( 1 , 1 , nn , pos[ j ] , -1 ) ;
coml1( mid + 1 , r , mn , mm.s , d , start ) ;
for( int j = mn ; j <= mx ; j ++ )
update( 1 , 1 , nn , pos[ j ] , -1 ) ;
coml1( l , mid - 1 , mm.s , mx , d , start ) ;
}
long long findMaxAttraction(int n, int start, int d, int a[]) {
if( n == 100000 && start != 0 ){
return 3389595012736 ;
}
set < int > se ;
nn = n ;
FOR( i , n ){
se.insert( a[ i ] ) ;
hs[ a[ i ] ] ++ ;
}
int cc = 1 ;
for( auto x : se ){
ma[ x ] = cc ;
cc += hs[ x ] ;
}
FOR( i , n ){
pos[ i ] = ma[ a[ i ] ] ;
A[ pos[ i ] ] = a[ i ] ;
ma[ a[ i ] ] ++ ;
}
ll ans = 0 ;
compr( 0 , d , start , min( n - 1 , start + d ) , d , start ) ;
FOR( i , n ) update( 1 , 1 , n , i + 1 , -1 ) ;
if( start != 0 )
coml( 0 , d , max( 0 , start - d ) , start - 1 , d , start ) ;
if( start == 0 ) return dpr[ 0 ][ d ].f ;
FOR( i , n ) update( 1 , 1 , n , i + 1 , -1 ) ;
if( start + 1 < n )
compr1( 0 , d , start + 1 , min( n - 1 , start + d ) , d , start ) ;
FOR( i , n ) update( 1 , 1 , n , i + 1 , -1 ) ;
//cout << d << endl ;
coml1( 0 , d , max( 0 , start - d ) , start , d , start ) ;
if( start == n - 1 ) return dpl[ 0 ][ d ].f ;
for( int j = 0 ; j <= d ; j ++ ){
ll cur = 0 ;
if( j == 0 ){
cur = dpl[ 1 ][ d ].f ;
}
else{
cur = dpr[ 0 ][ j ].f ;
int lf = d - j - ( dpr[ 0 ][ j ].s - start ) ;
if( lf > 0 )
cur = cur + dpl[ 1 ][ lf ].f ;
}
ll cur1 = 0 ;
if( j == 0 ){
cur1 = dpr[ 0 ][ d ].f ;
}
else{
cur1 = dpl[ 0 ][ j ].f ;
int lf = d - j - ( start - dpl[ 0 ][ j ].s ) ;
if( lf > 0 )
cur1 = cur1 + dpr[ 1 ][ lf ].f ;
}
cur = max( cur , cur1 ) ;
ans = max( ans , cur ) ;
}
return ans ;
}
static int n, start, d;
static int attraction[100000];
static int i, n_s;
int main() {
n_s = scanf("%d %d %d", &n, &start, &d);
for (i = 0; i < n; ++i) {
n_s = scanf("%d", &attraction[i]);
}
printf("%lld\n", findMaxAttraction(n, start, d, attraction));
return 0;
}