제출 #1032562

#제출 시각아이디문제언어결과실행 시간메모리
1032562Gabriel모임들 (IOI18_meetings)C++17
17 / 100
92 ms19012 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...