Submission #776764

#	Time	Username	Problem	Language	Result	Execution time	Memory
776764		lollipop	Rice Hub (IOI11_ricehub)	C++17	68 / 100	1049 ms	8540 KiB

ricehub

#include "ricehub.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define int 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 ;
pair < int , int > sm[ N ] ;
set < pair < int , int > > se ;
pair < int , int > get_sum( int l , int r , int x ){
	int L , R ; 
	if( l > r ) return { 0 , 0 } ; 
	pair < int , int > p ;
	p = *( -- se.end() ) ;
	if( p.f < l ) return { 0 , 0 } ;  
	p = *(se.lower_bound( { l , -1 } ) ) ;
	L = p.s ;
	if( p.f > r ) return { 0 , 0 } ;
	p = *(--se.lower_bound( { r + 1 , -1 } ) ) ;
	R = p.s ; 
	p = sm[ R ] ;
	if( L != 0 ){
		p.f -= sm[ L - 1 ].f ;
		p.s -= sm[ L - 1 ].s ; 
	} 
	if( l <= x ){
		p.f = p.s * x - p.f ;
	}
	else{
		p.f = p.f - p.s * x ; 
	}
	return p ; 
}
int mx ;
int check( int x , int R ){
	int l = x - R , r = x + R ;
	pair < int , int > cur = get_sum( l , x , x ) ;
	pair < int , int > p = get_sum( x + 1 , r , x ) ;
	cur.f += p.f ; cur.s += p.s ;  
	if( cur.f <= mx ) return cur.s ; 
	int R1 = R - 1 ; 
	 l = x - R1 , r = x + R1 ;
	cur = get_sum( l , x , x ) ;
	p = get_sum( x + 1 , r , x ) ;	
	cur.f += p.f ; cur.s += p.s ; 
	if( cur.f + R > mx ) return -1 ;
	int lf = ( mx - cur.f ) ;
	cur.s = cur.s + ( lf / R ) ; 
	return cur.s ; 	 
}
signed besthub(signed R, signed L, signed X[], long long B){
       int ans = 0 ; mx = B ; 
       FOR( i , R ){
       	se.insert( { X[ i ] , i } ) ; 
       	 if( i == 0 ){
       	 	sm[ i ] = { X[ i ] , 1 } ; 
       	 	continue ; 
		 }
		 sm[ i ] = sm[ i - 1 ] ;
		 sm[ i ].f += X[ i ] ;
		 sm[ i ].s += 1 ; 
	   }
       FOR( i , R ){
       	  int x = X[ i ] ;
       	  int l = 0 , r = L ;
       	  while( l <= r ){
       	    int mid = ( l + r ) / 2 ;
			int y = check( x , mid ) ;
			if( y == -1 ){
				r = mid - 1 ; 
				continue ; 
			} 	
			ans = max( ans , y ) ;
			l = mid + 1 ; 
		  }
	   }
       return ans ; 
}
//#define MAX_R  1000000
//static signed R, L;
//static long long B;
//static signed X[MAX_R];
//
//static void read_input()
//{
//  int i;
//  scanf("%d %d %lld",&R,&L,&B);
//  for(i=0; i<R; i++)
//    scanf("%d",&X[i]);
//}
//
//signed main()
//{
//  signed ans;
//  read_input();
//  ans = besthub(R,L,X,B);
//  printf("%d\n", ans);
//  return 0;
//}

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 26 / 26
• Subtask 4: 0 / 32