Capítulo 5: Estructuras de Datos

import sys

def resolver():
    # Lectura rápida de todos los datos desde sys.stdin
    entrada = sys.stdin.read().split()
    if not entrada:
        return

    cantidad_piezas = int(entrada[0])
    pesos_carne = [int(x) for x in entrada[1:cantidad_piezas + 1]]

    # Inicializamos las respuestas con -1 por defecto
    respuesta = [-1] * cantidad_piezas
    
    # Pila monótona para guardar los índices
    pila_indices = []

    # Recorremos la lista de derecha a izquierda
    for i in range(cantidad_piezas - 1, -1, -1):
        peso_actual = pesos_carne[i]

        # Limpiamos los elementos de la derecha que no sean estrictamente mayores
        while pila_indices and pesos_carne[pila_indices[-1]] <= peso_actual:
            pila_indices.pop()

        # Si queda algún elemento en la pila, ese es el más cercano y más pesado
        if pila_indices:
            respuesta[i] = pila_indices[-1] + 1  # 1-based index

        # Guardamos el índice actual en la pila
        pila_indices.append(i)

    # Imprimimos la lista de respuestas separada por espacios
    print(*(respuesta))

if __name__ == "__main__":
    resolver()

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.ArrayDeque;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        // Entrada rápida usando BufferedReader
        BufferedReader lector = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens = new StringTokenizer(lector.readLine());

        if (!tokens.hasMoreTokens()) return;
        int cantidadPiezas = Integer.parseInt(tokens.nextToken());

        long[] pesosCarne = new long[cantidadPiezas];
        tokens = new StringTokenizer(lector.readLine());
        for (int i = 0; i < cantidadPiezas; i++) {
            pesosCarne[i] = Long.parseLong(tokens.nextToken());
        }

        int[] respuesta = new int[cantidadPiezas];
        Arrays.fill(respuesta, -1);

        // Usamos ArrayDeque como pila (más rápido que java.util.Stack)
        ArrayDeque<Integer> pilaIndices = new ArrayDeque<>();

        // Procesa la fila de carnes de derecha a izquierda
        for (int i = cantidadPiezas - 1; i >= 0; i--) {
            while (!pilaIndices.isEmpty() && pesosCarne[pilaIndices.peek()] <= pesosCarne[i]) {
                pilaIndices.pop();
            }

            if (!pilaIndices.isEmpty()) {
                respuesta[i] = pilaIndices.peek() + 1; // Convertimos a 1-based index
            }

            pilaIndices.push(i);
        }

        // Salida rápida con PrintWriter
        PrintWriter escritor = new PrintWriter(System.out);
        for (int i = 0; i < cantidadPiezas; i++) {
            escritor.print(respuesta[i] + (i == cantidadPiezas - 1 ? "" : " "));
        }
        escritor.println();
        escritor.flush();
    }
}

import sys

def resolver():
    entrada = sys.stdin.read().split()
    if not entrada:
        return

    num_columnas = int(entrada[0])
    altura_columna = [int(x) for x in entrada[1:num_columnas + 1]]

    limite_izquierdo = [0] * num_columnas
    limite_derecho = [0] * num_columnas
    pila_indices = []

    # 1. Calculamos el límite izquierdo para cada columna
    for i in range(num_columnas):
        while pila_indices and altura_columna[pila_indices[-1]] >= altura_columna[i]:
            pila_indices.pop()
        
        limite_izquierdo[i] = pila_indices[-1] if pila_indices else -1
        pila_indices.append(i)

    # Vaciamos la pila
    pila_indices.clear()

    # 2. Calculamos el límite derecho para cada columna
    for i in range(num_columnas - 1, -1, -1):
        while pila_indices and altura_columna[pila_indices[-1]] >= altura_columna[i]:
            pila_indices.pop()
        
        limite_derecho[i] = pila_indices[-1] if pila_indices else num_columnas
        pila_indices.append(i)

    # 3. Calculamos la máxima área posible
    area_maxima = 0
    for i in range(num_columnas):
        ancho_cartel = limite_derecho[i] - limite_izquierdo[i] - 1
        area_actual = altura_columna[i] * ancho_cartel
        if area_actual > area_maxima:
            area_maxima = area_actual

    print(area_maxima)

if __name__ == "__main__":
    resolver()

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader lector = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens = new StringTokenizer(lector.readLine());

        if (!tokens.hasMoreTokens()) return;
        int numColumnas = Integer.parseInt(tokens.nextToken());

        long[] alturaColumna = new long[numColumnas];
        tokens = new StringTokenizer(lector.readLine());
        for (int i = 0; i < numColumnas; i++) {
            alturaColumna[i] = Long.parseLong(tokens.nextToken());
        }

        int[] limiteIzquierdo = new int[numColumnas];
        int[] limiteDerecho = new int[numColumnas];
        ArrayDeque<Integer> pilaIndices = new ArrayDeque<>();

        // 1. Calculamos el límite izquierdo para cada columna
        for (int i = 0; i < numColumnas; i++) {
            while (!pilaIndices.isEmpty() && alturaColumna[pilaIndices.peek()] >= alturaColumna[i]) {
                pilaIndices.pop();
            }
            limiteIzquierdo[i] = pilaIndices.isEmpty() ? -1 : pilaIndices.peek();
            pilaIndices.push(i);
        }

        pilaIndices.clear();

        // 2. Calculamos el límite derecho para cada columna
        for (int i = numColumnas - 1; i >= 0; i--) {
            while (!pilaIndices.isEmpty() && alturaColumna[pilaIndices.peek()] >= alturaColumna[i]) {
                pilaIndices.pop();
            }
            limiteDerecho[i] = pilaIndices.isEmpty() ? numColumnas : pilaIndices.peek();
            pilaIndices.push(i);
        }

        // 3. Buscamos el área máxima
        long areaMaxima = 0;
        for (int i = 0; i < numColumnas; i++) {
            long anchoCartel = limiteDerecho[i] - limiteIzquierdo[i] - 1;
            long areaActual = alturaColumna[i] * anchoCartel;
            areaMaxima = Math.max(areaMaxima, areaActual);
        }

        PrintWriter escritor = new PrintWriter(System.out);
        escritor.println(areaMaxima);
        escritor.flush();
    }
}

import sys
import bisect

def resolver():
    entrada = sys.stdin.read().split()
    if not entrada:
        return

    num_camisetas = int(entrada[0])
    num_participantes = int(entrada[1])

    idx = 2
    # Leemos e introducimos las camisetas en una lista estándar ordenada
    inventario = [int(x) for x in entrada[idx : idx + num_camisetas]]
    inventario.sort()
    idx += num_camisetas

    salida = []
    for _ in range(num_participantes):
        limite = int(entrada[idx])
        idx += 1

        # bisect_right nos da la posición del primer elemento > limite
        i = bisect.bisect_right(inventario, limite)

        if i == 0:
            salida.append("-1")
        else:
            # El elemento en i - 1 es el valor máximo <= limite
            valor_elegido = inventario[i - 1]
            salida.append(str(valor_elegido))
            # Eliminamos esa camiseta concreta de la lista
            del inventario[i - 1]

    print("\n".join(salida))

if __name__ == "__main__":
    resolver()

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader lector = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens = new StringTokenizer(lector.readLine());

        if (!tokens.hasMoreTokens()) return;
        int numCamisetas = Integer.parseInt(tokens.nextToken());
        int numParticipantes = Integer.parseInt(tokens.nextToken());

        // Simulamos un multiset en Java usando TreeMap
        TreeMap<Integer, Integer> inventarioCamisetas = new TreeMap<>();

        tokens = new StringTokenizer(lector.readLine());
        for (int i = 0; i < numCamisetas; i++) {
            int valor = Integer.parseInt(tokens.nextToken());
            inventarioCamisetas.put(valor, inventarioCamisetas.getOrDefault(valor, 0) + 1);
        }

        PrintWriter escritor = new PrintWriter(System.out);
        tokens = new StringTokenizer(lector.readLine());

        for (int i = 0; i < numParticipantes; i++) {
            int limite = Integer.parseInt(tokens.nextToken());

            // floorKey(limite) devuelve la clave más grande que sea <= limite
            Integer valorElegido = inventarioCamisetas.floorKey(limite);

            if (valorElegido == null) {
                escritor.println(-1);
            } else {
                escritor.println(valorElegido);
                
                // Reducimos el stock de esa camiseta en 1
                int cantidad = inventarioCamisetas.get(valorElegido);
                if (cantidad == 1) {
                    inventarioCamisetas.remove(valorElegido);
                } else {
                    inventarioCamisetas.put(valorElegido, cantidad - 1);
                }
            }
        }

        escritor.flush();
    }
}

import sys
import heapq

def resolver():
    entrada = sys.stdin.read().split()
    if not entrada:
        return

    n = int(entrada[0])
    
    # heapq en Python es nativamente un Min-Heap
    arroz = [int(x) for x in entrada[1:n + 1]]
    heapq.heapify(arroz)

    coste_total = 0

    # Mientras quede más de un recipiente
    while len(arroz) > 1:
        primero = heapq.heappop(arroz)
        segundo = heapq.heappop(arroz)

        suma = primero + segundo
        coste_total += suma

        # Insertamos de nuevo la mezcla en el Heap
        heapq.heappush(arroz, suma)

    print(coste_total)

if __name__ == "__main__":
    resolver()

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader lector = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens = new StringTokenizer(lector.readLine());

        if (!tokens.hasMoreTokens()) return;
        int n = Integer.parseInt(tokens.nextToken());

        // PriorityQueue en Java es por defecto un Min-Heap
        PriorityQueue<Long> minHeap = new PriorityQueue<>();

        tokens = new StringTokenizer(lector.readLine());
        for (int i = 0; i < n; i++) {
            minHeap.add(Long.parseLong(tokens.nextToken()));
        }

        long costeTotal = 0;

        while (minHeap.size() > 1) {
            long primero = minHeap.poll();
            long segundo = minHeap.poll();

            long suma = primero + segundo;
            costeTotal += suma;

            minHeap.add(suma);
        }

        PrintWriter escritor = new PrintWriter(System.out);
        escritor.println(costeTotal);
        escritor.flush();
    }
}

import sys

sys.setrecursionlimit(300000)

class DSU:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.sz = [1] * (n + 1)

    def find(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i == root_j:
            return False

        if self.sz[root_i] < self.sz[root_j]:
            root_i, root_j = root_j, root_i

        self.parent[root_j] = root_i
        self.sz[root_i] += self.sz[root_j]
        return True

    def same(self, i, j):
        return self.find(i) == self.find(j)

def resolver():
    entrada = sys.stdin.read().split()
    if not entrada:
        return

    n = int(entrada[0])
    q = int(entrada[1])

    dsu = DSU(n)
    salida = []

    idx = 2
    for _ in range(q):
        tipo = int(entrada[idx])
        u = int(entrada[idx + 1])
        v = int(entrada[idx + 2])
        idx += 3

        if tipo == 1:
            dsu.unite(u, v)
        else:
            if dsu.same(u, v):
                salida.append("YES")
            else:
                salida.append("NO")

    print("\n".join(salida))

if __name__ == "__main__":
    resolver()

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    static class DSU {
        int[] parent;
        int[] sz;

        public DSU(int n) {
            parent = new int[n + 1];
            sz = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                parent[i] = i;
                sz[i] = 1;
            }
        }

        public int find(int i) {
            if (parent[i] == i) return i;
            return parent[i] = find(parent[i]);
        }

        public boolean unite(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI == rootJ) return false;

            if (sz[rootI] < sz[rootJ]) {
                int temp = rootI; rootI = rootJ; rootJ = temp;
            }

            parent[rootJ] = rootI;
            sz[rootI] += sz[rootJ];
            return true;
        }

        public boolean same(int i, int j) {
            return find(i) == find(j);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader lector = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens;
        
        String linea = lector.readLine();
        if (linea == null) return;
        tokens = new StringTokenizer(linea);

        int n = Integer.parseInt(tokens.nextToken());
        int q = Integer.parseInt(tokens.nextToken());

        DSU dsu = new DSU(n);
        PrintWriter escritor = new PrintWriter(System.out);

        for (int i = 0; i < q; i++) {
            while (tokens == null || !tokens.hasMoreTokens()) {
                tokens = new StringTokenizer(lector.readLine());
            }

            int tipo = Integer.parseInt(tokens.nextToken());
            int u = Integer.parseInt(tokens.nextToken());
            int v = Integer.parseInt(tokens.nextToken());

            if (tipo == 1) {
                dsu.unite(u, v);
            } else {
                if (dsu.same(u, v)) {
                    escritor.println("YES");
                } else {
                    escritor.println("NO");
                }
            }
        }

        escritor.flush();
    }
}