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

Envío 4984

Problema 0xca - Contar cuantas veces aparece X en un subarreglo

  • Autor: Ikerlb
  • Fecha: 2021-10-04 19:33:13 UTC (Hace más de 2 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.154 s 13 KBi
#2
Correcto
0.362 s 12 KBi
#3
Tiempo límite excedido
1.123 s 26 KBi
#4
Tiempo límite excedido
1.254 s 97 KBi
#5
Tiempo límite excedido
1.154 s 97 KBi
#6
Tiempo límite excedido
1.071 s 109 KBi
#7
Tiempo límite excedido
1.323 s 47 KBi
#8
Tiempo límite excedido
1.05 s 37 KBi
Puntos totales: 25 / 100

Código

import java.util.HashMap;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;

class Main{
    public static int query(List<Integer> arr, int target){
        if(arr == null || target < 0)   
            return 0;
        int l = 0;              
        int r = arr.size() - 1;
        int res = -1;

        while(l <= r){
            int m = (l + r) >> 1; // safe because of bounds     
            if(arr.get(m) <= target){
                res = m;                    
                l = m + 1;
            } else {
                r = m - 1;      
            }   
        }
        return res + 1;
    }

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);   
        int N = scanner.nextInt();
        Map<Integer, List<Integer>> byElems = new HashMap<>();      

        for(int i = 0; i < N; i++){ 
            int elem = scanner.nextInt();               
            List<Integer> m = byElems.get(elem);
            if(m == null){  
                m = new ArrayList<>();
                byElems.put(elem, m);           
            }
            m.add(i);
        }

        int Q = scanner.nextInt();      
        int L, R, X, left, right;
        L = R = X = left = right = 0;
        for(int i = 0; i < Q; i++){
            L = scanner.nextInt();
            R = scanner.nextInt();
            X = scanner.nextInt();          
            left = query(byElems.get(X), L - 1);
            right = query(byElems.get(X), R);
            System.out.println(right - left);
        }
    }
}