█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 5189

Problema 0x9b - Máximo elemento en un subarreglo pequeño

  • Autor: DanielP
  • Fecha: 2021-10-26 04:02:17 UTC (Hace alrededor de 3 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.004 s 5 KBi
#2
Correcto
0.007 s 4 KBi
#3
Correcto
0.005 s 3 KBi
#4
Correcto
0.005 s 5 KBi
#5
Correcto
0.004 s 0 KBi
#6
Correcto
0.003 s 0 KBi
#7
Correcto
0.003 s 0 KBi
#8
Correcto
0.005 s 3 KBi
#9
Correcto
0.004 s 0 KBi
#10
Correcto
0.004 s 1 KBi
#11
Correcto
0.047 s 12 KBi
#12
Correcto
0.041 s 10 KBi
#13
Correcto
0.055 s 10 KBi
Puntos totales: 100 / 100

Código

/// Write by Daniel Perez .PERAPRO
#include<bits/stdc++.h>

using namespace std;
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(), s.end()
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using vi=vector<int>;
using vl=vector<ll>;
using pii=pair<int,int>;
char el = '\n';
char esp = ' ';

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

ostream& operator<<(ostream& os, const vector<int> &v){
    for(auto const &i: v){
        os<<i<<" ";
    }
    os<<'\n';
    return os;
}
string yes="YES";
string no="NO";

int n;
const int Log2 = 25;
const int N = 1e5+5;
int v[N];
int st[N][Log2];

void build(){
    for(int i=0;i<n;i++)
        st[i][0] = i;
        
    for(int j = 1;j < Log2;j++){
        for(int i=0;i + (1 << (j - 1)) < n;i++){
            if(v[st[i][j - 1]] >= v[st[i + (1 << (j - 1))][j - 1]])
                st[i][j] = st[i][j - 1];
            else
                st[i][j] = st[i + (1 << (j - 1))][j - 1];
        }
    }
}

int query(int l, int r){
    int x = 31 - __builtin_clz(r - l + 1);
    if(v[st[l][x]] >= v[st[r - (1<<x) + 1][x]])
        return st[l][x];
    return st[r - (1 << x) + 1][x];
}

int main(){
	fast_io;
	/*
 	freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    */
    cin>>n;
    
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    build();
    int q,l,r;
    cin>>q;
    
    while(q--){
        cin>>l>>r;
        cout<<query(l, r)<<el;
    }
}

/*

*/