oj.uz

Submission #942451

# Submission time Handle Problem Language Result Execution time Memory
942451 2024-03-10T16:26:47 Z vjudge1 Index (COCI21_index) C++17
20 / 110
 2500 ms 3980 KB 
#include "bits/stdc++.h"
using namespace std;
vector<long long> a;
struct Nodo{
    long long M_nimo, M_ximo;
};
vector<Nodo> _rbol;
void Crear(long long Izquierda, long long Derecha, long long Posici_n){
    if(Izquierda == Derecha){
        _rbol[Posici_n].M_nimo = a[Izquierda];
        _rbol[Posici_n].M_ximo = a[Izquierda];
    } else {
        long long Promedio = (Izquierda + Derecha) / 2;
        Crear(Izquierda, Promedio, Posici_n * 2);
        Crear(Promedio + 1, Derecha, Posici_n * 2 + 1);
        _rbol[Posici_n].M_nimo = min(_rbol[Posici_n * 2].M_nimo, _rbol[Posici_n * 2 + 1].M_nimo);
        _rbol[Posici_n].M_ximo = max(_rbol[Posici_n * 2].M_ximo, _rbol[Posici_n * 2 + 1].M_ximo);
    }
}
long long Consulta(long long Izquierda, long long Derecha, long long Posici_n, long long Inicio, long long Final, long long Valor){
    if(Izquierda > Final or Derecha < Inicio) return 0;
    else if(_rbol[Posici_n].M_nimo >= Valor and Izquierda >= Inicio and Derecha <= Final) return Derecha - Izquierda + 1;
    else if(_rbol[Posici_n].M_ximo < Valor) return 0;
    else {
        long long Promedio = (Izquierda + Derecha) / 2;
        return Consulta(Izquierda, Promedio, Posici_n * 2, Inicio, Final, Valor) + Consulta(Promedio + 1, Derecha, Posici_n * 2 + 1, Inicio, Final, Valor);
    }
}
/*long long Mayor(long long Izquierda, long long Derecha, long long Posici_n, long long Inicio, long long Final){
    if(Izquierda > Final or Derecha < Inicio) return 0;
    else if(Izquierda >= Inicio and Derecha <= Final) return _rbol[Posici_n].M_ximo;
    else {
        long long Promedio = (Izquierda + Derecha) / 2;
        return max(Mayor(Izquierda, Promedio, Posici_n * 2, Inicio, Final), Mayor(Promedio + 1, Derecha, Posici_n * 2 + 1, Inicio, Final));
    }
}*/
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    long long n, m;
    cin>>n>>m;
    a.assign(n, 0);
    Nodo E;
    E.M_nimo = -0;
    E.M_ximo = 0;
    _rbol.assign(n * 4, E);
    for(long long i = 0; i < n; i++) cin>>a[i];
    n--;
    Crear(0, n, 1);
    while(m--){
        long long l, r;
        cin>>l>>r;
        l--;
        r--;
        long long Mejor = 1;
        long long Izquierda = 2;
        long long Derecha = r - l + 1;
        while(1){
            long long Promedio = (Izquierda + Derecha) / 2;
            if(Consulta(0, n, 1, l, r, Promedio) < Promedio) Derecha = Promedio - 1;
            else {
                Mejor = Promedio;
                Izquierda = Promedio + 1;
            }
            if(Izquierda >= Derecha + 1) break;
        }
        cout<<Mejor<<"\n";
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 348 KB Output is correct
2 Correct 32 ms 344 KB Output is correct
3 Correct 33 ms 348 KB Output is correct
4 Correct 33 ms 528 KB Output is correct
5 Correct 32 ms 600 KB Output is correct
6 Correct 36 ms 600 KB Output is correct
7 Correct 32 ms 348 KB Output is correct
8 Correct 32 ms 344 KB Output is correct
9 Correct 39 ms 344 KB Output is correct
10 Correct 35 ms 508 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 348 KB Output is correct
2 Correct 32 ms 344 KB Output is correct
3 Correct 33 ms 348 KB Output is correct
4 Correct 33 ms 528 KB Output is correct
5 Correct 32 ms 600 KB Output is correct
6 Correct 36 ms 600 KB Output is correct
7 Correct 32 ms 348 KB Output is correct
8 Correct 32 ms 344 KB Output is correct
9 Correct 39 ms 344 KB Output is correct
10 Correct 35 ms 508 KB Output is correct
11 Execution timed out 2515 ms 3980 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 348 KB Output is correct
2 Correct 32 ms 344 KB Output is correct
3 Correct 33 ms 348 KB Output is correct
4 Correct 33 ms 528 KB Output is correct
5 Correct 32 ms 600 KB Output is correct
6 Correct 36 ms 600 KB Output is correct
7 Correct 32 ms 348 KB Output is correct
8 Correct 32 ms 344 KB Output is correct
9 Correct 39 ms 344 KB Output is correct
10 Correct 35 ms 508 KB Output is correct
11 Execution timed out 2515 ms 3980 KB Time limit exceeded
12 Halted 0 ms 0 KB -