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 "ricehub.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> pr, x;
ll check(ll l, ll r, ll mid){
int st = l, en = r, be = -1;
while (st <= en){
int mi = (st + en) / 2;
if (x[mi] <= mid){
st = mi + 1;
be = mi;
}
else{
en = mi - 1;
}
}
ll su = mid * (be - l + 1) - (pr[be] - pr[l - 1]);
su += (pr[r] - pr[be]) - mid * (r - be + 1);
return su;
}
int besthub(int R, int L, int X[], long long B)
{
pr.assign(R + 1, 0), x.assign(R + 1, 0);
for (int i = 1; i <= R; i++){
x[i] = X[i - 1];
pr[i] = pr[i - 1] + x[i];
}
ll l = 1, r = 1, ans = 0;
while(r <= R){
int mid = (x[l] + x[r]) / 2, mi1, mi2;
auto it = upper_bound(x.begin(), x.end(), mid);
if (it == x.end()){
mi1 = mi2 = R;
}
else{
mi2 = it - x.begin();
mi1 = mi2 - 1;
}
ll va = min(check(l, r, mi1), check())
}
return ans;
}*/
#include "ricehub.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> pr, x;
ll check(ll l, ll r, ll mid){
int st = l, en = r, be = -1;
while (st <= en){
int mi = (st + en) / 2;
if (x[mi] <= mid){
st = mi + 1;
be = mi;
}
else{
en = mi - 1;
}
}
ll su = x[be] * (be - l + 1) - (pr[be] - pr[l - 1]);
su += (pr[r] - pr[be]) - x[be] * (r - be + 1);
return su;
}
int besthub(int R, int L, int X[], long long B)
{
pr.assign(R + 1, 0), x.assign(R + 1, 0);
for (int i = 1; i <= R; i++){
x[i] = X[i - 1];
pr[i] = pr[i - 1] + x[i];
}
ll l = 1, r = 1, ans = 0;
while(r <= R){
if ((x[r] + x[l]) % 2 == 1){
int mi1 = (x[l] + x[r]) / 2, mi2 = (x[l] + x[r]) / 2 + 1;
ll va1 = check(l, r, mi1), va2 = check(l, r, mi2);
if (va1 > va2){
swap(va1, va2);
}
if (va1 > B){
l++;
}
else if (va1 <= B){
r++;
ans = max(ans, (r - l));
}
}
else{
int mi = (x[l] + x[r]) / 2;
ll va = check(l, r, mi);
if (va > B){
l++;
}
else{
r++;
ans = max(ans, (r - l));
}
}
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |