Submission #1032562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032562		Gabriel	Meetings (IOI18_meetings)	C++17	17 / 100	92 ms	19012 KiB

meetings

#include "meetings.h"
#include "bits/stdc++.h"
using namespace std;
struct Nodo{
  long long Segmento, Suma, Izquierda, Derecha;
};
vector<long long> h;
vector<Nodo> _rbol;
Nodo Combinar(Nodo a, Nodo b){
  Nodo e;
  e.Suma = a.Suma + b.Suma;
  e.Izquierda = max(a.Izquierda, a.Suma + b.Izquierda);
  e.Derecha = max(b.Derecha, b.Suma + a.Derecha);
  e.Segmento = max(a.Derecha + b.Izquierda, max(a.Segmento, b.Segmento));
  return e;
}
void Crear(long long Inicio, long long Final, long long Posici_n){
  if(Inicio == Final){
    _rbol[Posici_n].Suma = h[Inicio];
    _rbol[Posici_n].Segmento = max(0LL, h[Inicio]);
    _rbol[Posici_n].Izquierda = max(0LL, h[Inicio]);
    _rbol[Posici_n].Derecha = max(0LL, h[Inicio]);
  } else {
    long long Promedio = (Inicio + Final) / 2;
    Crear(Inicio, Promedio, Posici_n * 2);
    Crear(Promedio + 1, Final, Posici_n * 2 + 1);
    _rbol[Posici_n] = Combinar(_rbol[Posici_n * 2], _rbol[Posici_n * 2 + 1]);
  }
}
Nodo Consulta(long long Izquierda, long long Derecha, long long Posici_n, long long Inicio, long long Final){
  if(Izquierda >= Inicio and Derecha <= Final){
    return _rbol[Posici_n];
  }
  if(Izquierda > Final or Derecha < Inicio){
    Nodo E;
    E.Suma = 0;
    E.Segmento = 0;
    E.Izquierda = 0;
    E.Derecha = 0;
    return E;
  }
  long long Promedio = (Izquierda + Derecha) / 2;
  Nodo Izquierdo = Consulta(Izquierda, Promedio, Posici_n * 2, Inicio, Final);
  Nodo Derecho = Consulta(Promedio + 1, Derecha, Posici_n * 2 + 1, Inicio, Final);
  Nodo E = Combinar(Izquierdo, Derecho);
  return E;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
  long long n = H.size() - 1;
  bool _1_2 = 1;
  for(long long i = 0; i <= n; i++){
    h.push_back((long long)H[i]);
    if(h[i] != 1 and h[i] != 2) _1_2 = 0;
  }
  if(_1_2){
    for(long long i = 0; i <= n; i++){
      if(h[i] == 2) h[i] = -22222222;
    }
  }
  long long q = L.size();
  Nodo E;
  E.Suma = 0;
  E.Segmento = 0;
  E.Izquierda = 0;
  E.Derecha = 0;
  _rbol.assign(n * 4 + 22, E);
  Crear(0, n, 1);
  //cerr<<"Vas bien\n";
  vector<long long> Respuesta(q);
  for(long long i = 0; i < q; i++){
    long long l = L[i];
    long long r = R[i];
    if(_1_2) Respuesta[i] = 2 * (r - l + 1) - Consulta(0, n, 1, l, r).Segmento;
  }
  return Respuesta;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 17 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40