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

Envío 5192

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

  • Autor: Ikerlb
  • Fecha: 2021-10-26 07:42:39 UTC (Hace más de 2 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.026 s 3 KBi
#2
Correcto
0.025 s 3 KBi
#3
Correcto
0.027 s 3 KBi
#4
Correcto
0.03 s 3 KBi
#5
Correcto
0.027 s 3 KBi
#6
Correcto
0.024 s 3 KBi
#7
Correcto
0.032 s 3 KBi
#8
Correcto
0.028 s 3 KBi
#9
Correcto
0.027 s 3 KBi
#10
Correcto
0.043 s 3 KBi
#11
Correcto
0.347 s 20 KBi
#12
Correcto
0.343 s 20 KBi
#13
Correcto
0.394 s 20 KBi
Puntos totales: 100 / 100

Código

# kinda feel like using segment trees

class SegmentTree:
    def __init__(self, arr):
        self.arr = arr
        self.tree = [0 for _ in range(4 * len(arr))]
        self._build_tree(1, 0, len(arr) - 1)

    def _build_tree(self, i, l, r):
        if l == r:
            self.tree[i] = (self.arr[l], l)
            return self.tree[i]
        mid = (l + r) >> 1
        lsq = self._build_tree(2 * i, l, mid)
        rsq = self._build_tree(2 * i + 1, mid + 1, r)
        self.tree[i] = max(lsq, rsq, key = lambda x: (x[0], -x[1]))
        return self.tree[i]

    def query(self, l, r):
        return self._query(1, l, r, 0, len(self.arr) - 1)[1]


    def _query(self, i, l, r, ll, rr):
        if ll == l and rr == r:
            return self.tree[i]
        mid = (ll + rr) >> 1
        if r <= mid:
            return self._query(2 * i, l, r, ll, mid)
        elif l > mid:
            return self._query(2 * i + 1, l, r, mid + 1, rr)
        lsq = self._query(2 * i, l, mid, ll, mid)
        rsq = self._query(2 * i + 1, mid + 1, r, mid + 1, rr)
        return max(lsq, rsq, key = lambda x: (x[0], -x[1]))

    def __repr__(self):
        return f"arr: {self.arr} tree: {self.tree}"

N = int(input())

arr = list(map(int, input().split(" ")))
st = SegmentTree(arr)

Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split(" "))
    print(st.query(l, r))