oj.uz

Submission #1110538

# Submission time Handle Problem Language Result Execution time Memory
1110538 2024-11-09T21:09:51 Z Gabriel Rice Hub (IOI11_ricehub) C++17
0 / 100
 1000 ms 10952 KB 
#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

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()){
      |        ~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Incorrect 1 ms 336 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 504 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Incorrect 1 ms 336 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 3 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 5 ms 336 KB Output is correct
8 Correct 3 ms 532 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Incorrect 2 ms 336 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 2128 KB Output is correct
2 Correct 107 ms 2128 KB Output is correct
3 Correct 987 ms 9944 KB Output is correct
4 Execution timed out 1004 ms 10952 KB Time limit exceeded
5 Halted 0 ms 0 KB -