#include "ricehub.h"
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <map>
#include <vector>
using namespace std ;
const int N = 2e5 ;
long long ac[N], ac2[N] ;
map<int,int> ap;
vector <int> nw ;
map<int,int> ap2 ;
int lst[N] ;
int besthub(int R, int L, int X[], long long B)
{
for ( int i = 0 ; i < R ; ++i ) if ( !ap.count(X[i]) ) nw.push_back(X[i]), ap[X[i]] = i ;
int sz = nw.size() ;
for ( int i = 0 ; i < sz ; ++i ) ap2[nw[i]] = i, lst[i] = ap[nw[i]] ;
for ( int i = 1 ; i < R ; ++i ) ac[i] = ac[i-1] + 1ll * (X[i] - X[i-1]) * i;
for ( int i = R-2 ; i >= 0 ; --i ) ac2[i] = ac2[i+1] + 1ll * (X[i+1] - X[i]) * (R-i-1) ;
int ans = 0 ;
for ( int i = 0 ; i < R ; ++i ) {
int lw = i, hg = R-1 ;
while ( lw <= hg ) {
int mid = (lw + hg) >> 1 ;
int lw2 = ap2[X[i]], hg2 = sz-1 ;
int mid2 ;
long long cost ;
while ( lw2 < hg2 ) {
int mid2a = (lw2 + hg2) >> 1 ;
mid2 = lst[mid2a] ;
cost = ac[mid2] - 1ll * i * (X[mid2] - X[i]) - ac[i] + ac2[mid2] - 1ll * (R-mid-1) * (X[mid] - X[mid2]) - ac2[mid];
mid2a++ ;
mid2 = lst[mid2a] ;
long long cost2 = ac[mid2] - 1ll * i * (X[mid2] - X[i]) - ac[i] + ac2[mid2] - 1ll * (R-mid-1) * (X[mid] - X[mid2]) - ac2[mid];
// cout << i << " " << mid2 << " " <<mid << " cost " << cost << " " << cost2 << endl ;
if ( cost >= cost2 ) lw2 = mid2a ;
else hg2 = mid2a-1 ;
}
mid2 = lst[lw2] ;
cost = ac[mid2] - 1ll * i * (X[mid2] - X[i]) - ac[i] + ac2[mid2] - 1ll * (R-mid-1) * (X[mid] - X[mid2]) - ac2[mid];
//cout << i << " " << mid2 << " " <<mid << " cost " << cost << endl ;
if ( cost <= B ) lw = mid+1 ;
else hg = mid-1 ;
}
//cout << i << " " << hg << endl ;
ans = max ( ans, hg - i + 1 ) ;
}
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
0 ms |
384 KB |
Output is correct |
| 12 |
Correct |
0 ms |
384 KB |
Output is correct |
| 13 |
Correct |
1 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Correct |
1 ms |
384 KB |
Output is correct |
| 17 |
Correct |
0 ms |
384 KB |
Output is correct |
| 18 |
Correct |
1 ms |
384 KB |
Output is correct |
| 19 |
Correct |
1 ms |
384 KB |
Output is correct |
| 20 |
Correct |
1 ms |
384 KB |
Output is correct |
| 21 |
Correct |
1 ms |
384 KB |
Output is correct |
| 22 |
Correct |
1 ms |
384 KB |
Output is correct |
| 23 |
Correct |
1 ms |
384 KB |
Output is correct |
| 24 |
Correct |
1 ms |
384 KB |
Output is correct |
| 25 |
Correct |
1 ms |
384 KB |
Output is correct |
| 26 |
Correct |
1 ms |
384 KB |
Output is correct |
| 27 |
Correct |
1 ms |
384 KB |
Output is correct |
| 28 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
2 ms |
384 KB |
Output is correct |
| 12 |
Correct |
2 ms |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
512 KB |
Output is correct |
| 14 |
Correct |
2 ms |
512 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Correct |
1 ms |
384 KB |
Output is correct |
| 17 |
Correct |
2 ms |
384 KB |
Output is correct |
| 18 |
Correct |
2 ms |
384 KB |
Output is correct |
| 19 |
Correct |
2 ms |
512 KB |
Output is correct |
| 20 |
Correct |
3 ms |
640 KB |
Output is correct |
| 21 |
Correct |
5 ms |
512 KB |
Output is correct |
| 22 |
Correct |
5 ms |
512 KB |
Output is correct |
| 23 |
Correct |
10 ms |
896 KB |
Output is correct |
| 24 |
Correct |
10 ms |
896 KB |
Output is correct |
| 25 |
Correct |
12 ms |
1152 KB |
Output is correct |
| 26 |
Correct |
11 ms |
1024 KB |
Output is correct |
| 27 |
Correct |
11 ms |
1024 KB |
Output is correct |
| 28 |
Correct |
11 ms |
1024 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
59 ms |
2816 KB |
Output is correct |
| 2 |
Correct |
58 ms |
2816 KB |
Output is correct |
| 3 |
Correct |
408 ms |
12540 KB |
Output is correct |
| 4 |
Correct |
394 ms |
12528 KB |
Output is correct |
| 5 |
Correct |
77 ms |
1408 KB |
Output is correct |
| 6 |
Correct |
74 ms |
1408 KB |
Output is correct |
| 7 |
Correct |
203 ms |
2816 KB |
Output is correct |
| 8 |
Correct |
203 ms |
2852 KB |
Output is correct |
| 9 |
Correct |
119 ms |
2344 KB |
Output is correct |
| 10 |
Correct |
118 ms |
2304 KB |
Output is correct |
| 11 |
Correct |
414 ms |
12656 KB |
Output is correct |
| 12 |
Correct |
408 ms |
12528 KB |
Output is correct |
| 13 |
Correct |
185 ms |
6384 KB |
Output is correct |
| 14 |
Correct |
197 ms |
6260 KB |
Output is correct |
| 15 |
Correct |
318 ms |
9432 KB |
Output is correct |
| 16 |
Correct |
285 ms |
9460 KB |
Output is correct |
| 17 |
Correct |
346 ms |
11120 KB |
Output is correct |
| 18 |
Correct |
358 ms |
11120 KB |
Output is correct |
| 19 |
Correct |
367 ms |
11888 KB |
Output is correct |
| 20 |
Correct |
365 ms |
11884 KB |
Output is correct |
