| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1176323 | pera | Rice Hub (IOI11_ricehub) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include "ricehub.h"
#define LL long long
using namespace std;
int besthub(int R , int L , int X[] , int B){
vector<LL> p(R);
for(int i = 0;i < R;i ++){
if(i > 0){
p[i] = p[i - 1];
}
p[i] += X[i];
}
auto range_sum = [&](int l , int r){
if(l > r){
return 0LL;
}
return p[r] - (l > 0 ? p[l - 1] : 0);
};
int ans = 0;
for(int i = 0;i < R;i ++){
int ll , rr;
LL t = 0 , S = 0;
for(int bit = 30;bit >= 0;bit --){
t += 1 << bit;
int l = i , r = i;
for(int BIT = 20;BIT >= 0;BIT --){
l -= 1 << BIT;
if(l < 0 || X[l] < X[i] - t){
l += 1 << BIT;
}
r += 1 << BIT;
if(r >= R || X[r] > X[i] + t){
r -= 1 << BIT;
}
}
LL sL = (i - l) * X[i] - range_sum(l , i - 1);
LL sR = range_sum(i + 1 , r) - (r - i) * X[i];
if(sL + sR > B){
t -= 1 << bit;
}else{
ll = l;
rr = r;
S = sL + sR;
}
}
int old_l = ll , old_r = rr;
ans = max(ans , rr - ll + 1);
for(int bit = 20;bit >= 0;bit --){
rr += 1 << bit;
if(rr >= R){
rr -= 1 << bit;
}else{
LL E = range_sum(old_r + 1 , rr) - (rr - old_r) * X[i];
if(S + E > B){
rr -= 1 << bit;
}else{
ans = max(ans , rr - old_l + 1);
}
}
ll -= 1 << bit;
if(ll < 0){
ll += 1 << bit;
}else{
LL E = (old_l - ll) * X[i] - range_sum(ll , old_l - 1);
if(S + E > B){
ll += 1 << bit;
}else{
ans = max(ans , old_r - ll + 1);
}
}
}
}
return ans;
}