답안 #1110537

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1110537	2024-11-09T21:07:00 Z	Gabriel	쌀 창고 (IOI11_ricehub)	C++17	68 / 100	1000 ms	10952 KB

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

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.0 / 17.0

#	결과	실행 시간	메모리	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	452 KB	Output is correct

Subtask #2

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	504 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	504 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	508 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	336 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	1 ms	336 KB	Output is correct
15	Correct	1 ms	336 KB	Output is correct
16	Correct	1 ms	336 KB	Output is correct
17	Correct	1 ms	336 KB	Output is correct
18	Correct	1 ms	336 KB	Output is correct
19	Correct	1 ms	336 KB	Output is correct
20	Correct	1 ms	336 KB	Output is correct
21	Correct	2 ms	336 KB	Output is correct
22	Correct	2 ms	336 KB	Output is correct
23	Correct	2 ms	336 KB	Output is correct
24	Correct	2 ms	336 KB	Output is correct
25	Correct	2 ms	492 KB	Output is correct
26	Correct	2 ms	336 KB	Output is correct
27	Correct	2 ms	336 KB	Output is correct
28	Correct	2 ms	336 KB	Output is correct

Subtask #3

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	504 KB	Output is correct
3	Correct	3 ms	508 KB	Output is correct
4	Correct	5 ms	336 KB	Output is correct
5	Correct	2 ms	336 KB	Output is correct
6	Correct	2 ms	492 KB	Output is correct
7	Correct	3 ms	452 KB	Output is correct
8	Correct	3 ms	336 KB	Output is correct
9	Correct	2 ms	336 KB	Output is correct
10	Correct	2 ms	336 KB	Output is correct
11	Correct	3 ms	528 KB	Output is correct
12	Correct	3 ms	336 KB	Output is correct
13	Correct	3 ms	336 KB	Output is correct
14	Correct	3 ms	540 KB	Output is correct
15	Correct	3 ms	504 KB	Output is correct
16	Correct	2 ms	336 KB	Output is correct
17	Correct	3 ms	336 KB	Output is correct
18	Correct	3 ms	336 KB	Output is correct
19	Correct	3 ms	336 KB	Output is correct
20	Correct	3 ms	336 KB	Output is correct
21	Correct	20 ms	964 KB	Output is correct
22	Correct	21 ms	848 KB	Output is correct
23	Correct	21 ms	1016 KB	Output is correct
24	Correct	25 ms	848 KB	Output is correct
25	Correct	26 ms	848 KB	Output is correct
26	Correct	21 ms	936 KB	Output is correct
27	Correct	23 ms	848 KB	Output is correct
28	Correct	21 ms	1104 KB	Output is correct

Subtask #4

0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	115 ms	2244 KB	Output is correct
2	Correct	100 ms	2128 KB	Output is correct
3	Execution timed out	1066 ms	10952 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-