Submission #915237

#	Time	Username	Problem	Language	Result	Execution time	Memory
915237		vjudge1	3D Histogram (COCI20_histogram)	C++17	20 / 110	2504 ms	21840 KiB

histogram

#include "bits/stdc++.h"
using namespace std;
vector<long long> Bases;
vector<long long> Alturas;
vector<long long> _rbol_bases;
vector<long long> _rbol_alturas;
vector<long long> Jaja_bases;
vector<long long> Jaja_alturas;
void Crear_bases(long long Izquierda, long long Derecha, long long Posici_n){
    if(Izquierda == Derecha){
        _rbol_bases[Posici_n] = Bases[Izquierda];
        Jaja_bases[Izquierda] = Posici_n;
    } else {
        long long Promedio = (Izquierda + Derecha) / 2;
        Crear_bases(Izquierda, Promedio, Posici_n * 2);
        Crear_bases(Promedio + 1, Derecha, Posici_n * 2 + 1);
        _rbol_bases[Posici_n] = min(_rbol_bases[Posici_n * 2], _rbol_bases[Posici_n * 2 + 1]);
    }
}
long long Consulta_bases(long long Izquierda, long long Derecha, long long Posici_n, long long Inicio, long long Final){
    if(Izquierda >= Inicio and Derecha <= Final) return _rbol_bases[Posici_n];
    else if(Izquierda > Final or Derecha < Inicio) return 222222222222222;
    else {
        long long Promedio = (Izquierda + Derecha) / 2;
        return min(Consulta_bases(Izquierda, Promedio, Posici_n * 2, Inicio, Final), Consulta_bases(Promedio + 1, Derecha, Posici_n * 2 + 1, Inicio, Final));
    }
}
void Crear_alturas(long long Izquierda, long long Derecha, long long Posici_n){
    if(Izquierda == Derecha){
        _rbol_alturas[Posici_n] = Alturas[Izquierda];
        Jaja_alturas[Izquierda] = Posici_n;
    } else {
        long long Promedio = (Izquierda + Derecha) / 2;
        Crear_alturas(Izquierda, Promedio, Posici_n * 2);
        Crear_alturas(Promedio + 1, Derecha, Posici_n * 2 + 1);
        _rbol_alturas[Posici_n] = min(_rbol_alturas[Posici_n * 2], _rbol_alturas[Posici_n * 2 + 1]);
    }
}
long long Consulta_alturas(long long Izquierda, long long Derecha, long long Posici_n, long long Inicio, long long Final){
    if(Izquierda >= Inicio and Derecha <= Final) return _rbol_alturas[Posici_n];
    else if(Izquierda > Final or Derecha < Inicio) return 222222222222222;
    else {
        long long Promedio = (Izquierda + Derecha) / 2;
        return min(Consulta_alturas(Izquierda, Promedio, Posici_n * 2, Inicio, Final), Consulta_alturas(Promedio + 1, Derecha, Posici_n * 2 + 1, Inicio, Final));
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    long long n;
    cin>>n;
    Bases.assign(n, 0);
    Alturas.assign(n, 0);
    _rbol_bases.assign(n * 4, 0);
    _rbol_alturas.assign(n * 4, 0);
    Jaja_bases.assign(n, 0);
    Jaja_alturas.assign(n, 0);
    for(long long i = 0; i < n; i++) cin>>Bases[i]>>Alturas[i];
    n--;
    Crear_bases(0, n, 1);
    Crear_alturas(0, n, 1);
    long long Respuesta = -1;
    for(long long i = 0; i <= n; i++){
        for(long long j = i; j <= n; j++){
            long long Base = Consulta_bases(0, n, 1, i, j);
            long long Altura = Consulta_alturas(0, n, 1, i, j);
            long long Profundidad = j - i + 1;
            Respuesta = max(Respuesta, Base * Altura * Profundidad);
        }
    }
    cout<<Respuesta;
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 90