Submission #942451

#	Time	Username	Problem	Language	Result	Execution time	Memory
942451		vjudge1	Index (COCI21_index)	C++17	20 / 110	2515 ms	3980 KiB

index

#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 / 20
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50