Submission #1110537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110537		Gabriel	Rice Hub (IOI11_ricehub)	C++17	68 / 100	1066 ms	10952 KiB

ricehub

#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){
  _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;
      Actualizar(0, n, 1, 0, n, -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";*/
      Actualizar(0, n, 1, 0, n, 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:17:14: 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]
   17 |   if((p * 2) < _rbol.size()){
      |      ~~~~~~~~^~~~~~~~~~~~~~
ricehub.cpp:20:18: 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]
   20 |   if((p * 2 + 1) < _rbol.size()){
      |      ~~~~~~~~~~~~^~~~~~~~~~~~~~
ricehub.cpp: In function 'void Actualizar(long long int, long long int, long long int, long long int, long long int, long long int)':
ricehub.cpp:31:14: 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]
   31 |   if((p * 2) < _rbol.size()){
      |      ~~~~~~~~^~~~~~~~~~~~~~
ricehub.cpp:34:18: 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]
   34 |   if((p * 2 + 1) < _rbol.size()){
      |      ~~~~~~~~~~~~^~~~~~~~~~~~~~
ricehub.cpp:40: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]
   40 |     if((p * 2) < _rbol.size()){
      |        ~~~~~~~~^~~~~~~~~~~~~~
ricehub.cpp:43: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]
   43 |     if((p * 2 + 1) < _rbol.size()){
      |        ~~~~~~~~~~~~^~~~~~~~~~~~~~

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