| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 785821 |
2023-07-17T15:49:18 Z |
lollipop |
Holiday (IOI14_holiday) |
C++17 |
|
1377 ms |
23504 KB |
#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 = 3e5 + 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 = { 0 , start } ;
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 , start - 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 = { 0 , start + 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[]) {
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 ) ;
//cout << dpl[ 0 ][ d ].f ;
if( start == n - 1 ) return dpl[ 0 ][ d ].f ;
for( int j = 0 ; j <= d ; j ++ ){
ll cur = 0 ;
if( j == 0 ){
cur = dpl[ 0 ][ 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 ;
//cout << j << " " << cur << " " << dpr[ 0 ][ j ].f << endl ;
}
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);
// n = 100000 ; start = 99999 ; d = 250000 ;
// for (i = 0; i < n; ++i) {
// attraction[ i ] = 47551805 ;
// }
// printf("%lld\n", findMaxAttraction(n, start, d, attraction));
// return 0;
//}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Correct |
1 ms |
724 KB |
Output is correct |
| 4 |
Correct |
1 ms |
724 KB |
Output is correct |
| 5 |
Correct |
1 ms |
724 KB |
Output is correct |
| 6 |
Correct |
1 ms |
724 KB |
Output is correct |
| 7 |
Correct |
1 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
459 ms |
8696 KB |
Output is correct |
| 2 |
Correct |
583 ms |
8688 KB |
Output is correct |
| 3 |
Correct |
472 ms |
8644 KB |
Output is correct |
| 4 |
Correct |
521 ms |
8680 KB |
Output is correct |
| 5 |
Correct |
637 ms |
7524 KB |
Output is correct |
| 6 |
Correct |
171 ms |
4820 KB |
Output is correct |
| 7 |
Correct |
287 ms |
4468 KB |
Output is correct |
| 8 |
Correct |
387 ms |
4452 KB |
Output is correct |
| 9 |
Correct |
132 ms |
5516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
1608 KB |
Output is correct |
| 2 |
Correct |
20 ms |
1208 KB |
Output is correct |
| 3 |
Correct |
21 ms |
1580 KB |
Output is correct |
| 4 |
Correct |
19 ms |
1508 KB |
Output is correct |
| 5 |
Correct |
17 ms |
1460 KB |
Output is correct |
| 6 |
Correct |
7 ms |
980 KB |
Output is correct |
| 7 |
Correct |
4 ms |
852 KB |
Output is correct |
| 8 |
Correct |
5 ms |
852 KB |
Output is correct |
| 9 |
Correct |
4 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
986 ms |
17296 KB |
Output is correct |
| 2 |
Correct |
624 ms |
23504 KB |
Output is correct |
| 3 |
Correct |
255 ms |
10044 KB |
Output is correct |
| 4 |
Correct |
15 ms |
1268 KB |
Output is correct |
| 5 |
Correct |
4 ms |
852 KB |
Output is correct |
| 6 |
Correct |
5 ms |
852 KB |
Output is correct |
| 7 |
Correct |
5 ms |
724 KB |
Output is correct |
| 8 |
Correct |
1377 ms |
21148 KB |
Output is correct |
| 9 |
Correct |
1358 ms |
21168 KB |
Output is correct |
