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

Envío 5010

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

  • Autor: Ikerlb
  • Fecha: 2021-10-06 19:21:39 UTC (Hace más de 2 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.126 s 10 KBi
#2
Correcto
0.131 s 11 KBi
#3
Correcto
0.379 s 13 KBi
#4
Tiempo límite excedido
1.104 s 40 KBi
#5
Tiempo límite excedido
1.021 s 37 KBi
#6
Tiempo límite excedido
1.111 s 54 KBi
#7
Tiempo límite excedido
1.092 s 55 KBi
#8
Tiempo límite excedido
1.232 s 61 KBi
Puntos totales: 38 / 100

Código

import java.util.HashMap;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

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) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        Map<Integer, List<Integer>> byElems = new HashMap<>();      

        // First line is array size 
        String line = reader.readLine();
        StringTokenizer tokenizer = new StringTokenizer(line);
        int N = Integer.valueOf(tokenizer.nextToken());

        // Second line is array itself    
        line = reader.readLine();
        tokenizer = new StringTokenizer(line);
        for(int i = 0; i < N; i++){ 
            int elem = Integer.valueOf(tokenizer.nextToken());
            List<Integer> m = byElems.get(elem);
            if(m == null){  
                m = new ArrayList<>();
                byElems.put(elem, m);           
            }
            m.add(i);
        }

        // Third line is number of queries
        line = reader.readLine();
        tokenizer = new StringTokenizer(line);
        int Q = Integer.valueOf(tokenizer.nextToken()); 
        int L, R, X, left, right;
        L = R = X = left = right = 0;
        for(int i = 0; i < Q; i++){
            // a line per query
            line = reader.readLine();
            tokenizer = new StringTokenizer(line);
            L = Integer.valueOf(tokenizer.nextToken());
            R = Integer.valueOf(tokenizer.nextToken());
            X = Integer.valueOf(tokenizer.nextToken());
            left = query(byElems.get(X), L - 1);
            right = query(byElems.get(X), R);
            System.out.println(right - left);
        }
    }
}