oj.uz

Submission #915237

# Submission time Handle Problem Language Result Execution time Memory
915237 2024-01-23T14:38:00 Z vjudge1 3D Histogram (COCI20_histogram) C++17
20 / 110
 2500 ms 21840 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 636 KB Output is correct
2 Correct 495 ms 604 KB Output is correct
3 Correct 466 ms 848 KB Output is correct
4 Correct 451 ms 600 KB Output is correct
5 Correct 405 ms 600 KB Output is correct
6 Correct 498 ms 652 KB Output is correct
7 Correct 412 ms 600 KB Output is correct
8 Correct 441 ms 628 KB Output is correct
9 Correct 492 ms 636 KB Output is correct
10 Correct 475 ms 600 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 507 ms 656 KB Output is correct

Subtask #2
0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 636 KB Output is correct
2 Correct 495 ms 604 KB Output is correct
3 Correct 466 ms 848 KB Output is correct
4 Correct 451 ms 600 KB Output is correct
5 Correct 405 ms 600 KB Output is correct
6 Correct 498 ms 652 KB Output is correct
7 Correct 412 ms 600 KB Output is correct
8 Correct 441 ms 628 KB Output is correct
9 Correct 492 ms 636 KB Output is correct
10 Correct 475 ms 600 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 507 ms 656 KB Output is correct
13 Execution timed out 2504 ms 21840 KB Time limit exceeded
14 Halted 0 ms 0 KB -