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"
using namespace std;
vector<long long> a, _rbol, Deuda;
void Crear(long long i, long long f, long long p){
if(i == f){
_rbol[p] = a[i];
} else {
long long P = (i + f) / 2;
Crear(i, P, p * 2);
Crear(P + 1, f, p * 2 + 1);
_rbol[p] = _rbol[p * 2] + _rbol[p * 2 + 1];
}
}
long long Consulta(long long i, long long f, long long p, long long ii, long long ff){
if(Deuda[p] != -1){
_rbol[p] += (f - i + 1) * Deuda[p];
if((p * 2) < _rbol.size()){
Deuda[p * 2] += Deuda[p];
}
if((p * 2 + 1) < _rbol.size()){
Deuda[p * 2 + 1] += Deuda[p];
}
Deuda[p] = 0;
}
if(i >= ii and f <= ff) return _rbol[p];
if(i > ff or f < ii) return 0;
long long P = (i + f) / 2;
return Consulta(i, P, p * 2, ii, ff) + Consulta(P + 1, f, p * 2 + 1, ii, ff);
}
/*void Actualizar(long long i, long long f, long long p, long long ii, long long ff, long long v){
_rbol[p] += (f - i + 1) * Deuda[p];
if((p * 2) < _rbol.size()){
Deuda[p * 2] += Deuda[p];
}
if((p * 2 + 1) < _rbol.size()){
Deuda[p * 2 + 1] += Deuda[p];
}
Deuda[p] = 0;
if(i >= ii and f <= ff){
_rbol[p] += (f - i + 1) * v;
if((p * 2) < _rbol.size()){
Deuda[p * 2] += v;
}
if((p * 2 + 1) < _rbol.size()){
Deuda[p * 2 + 1] += v;
}
Deuda[p] = 0;
return;
}
if(i > ff or f < ii) return;
long long P = (i + f) / 2;
Actualizar(i, P, p * 2, ii, ff, v);
Actualizar(P + 1, f, p * 2 + 1, ii, ff, v);
}*/
int besthub(int R, int L, int X[], long long B){
long long n = R - 1;
_rbol.assign(R * 4, 0);
Deuda = _rbol;
for(long long i = 0; i <= n; i++){
a.push_back(X[i]);
}
Crear(0, n, 1);
int Mejor = -2;
for(long long i = 0; i <= n; i++){
long long Izquierda = i, Derecha = n, Tentativo = i;
while(1){
if(Izquierda >= (Derecha + 1)) break;
long long Promedio = (Izquierda + Derecha) / 2;
long long zd = (Promedio + i) / 2;
Deuda[1] -= a[zd];
long long Distancia = 0;
if(Promedio >= (zd + 1)) Distancia += Consulta(0, n, 1, zd + 1, Promedio);
if((zd - 1) >= i) Distancia -= Consulta(0, n, 1, i, zd - 1);
if(Distancia <= B){
Izquierda = Promedio + 1;
Tentativo = Promedio;
} else Derecha = Promedio - 1;
/*cout<<i<<" "<<Promedio<<" "<<Distancia<<"\n";
for(long long j = i; j <= Promedio; j++) cout<<Consulta(0, n, 1, j, j)<<" ";
cout<<"\n\n";
for(auto E: _rbol) cout<<E<<" ";
cout<<"\n";
for(auto E: Deuda) cout<<E<<" ";
cout<<"\n\n\n";*/
Deuda[1] += a[zd];
}
Mejor = max(Mejor, (int)(Tentativo - i + 1));
}
return Mejor;
}
Compilation message (stderr)
ricehub.cpp: In function 'long long int Consulta(long long int, long long int, long long int, long long int, long long int)':
ricehub.cpp:18:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | if((p * 2) < _rbol.size()){
| ~~~~~~~~^~~~~~~~~~~~~~
ricehub.cpp:21:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | if((p * 2 + 1) < _rbol.size()){
| ~~~~~~~~~~~~^~~~~~~~~~~~~~
# | 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... |