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

Envío 5021

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

  • Autor: Ikerlb
  • Fecha: 2021-10-06 20:56:36 UTC (Hace más de 2 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.252 s 11 KBi
#2
Correcto
0.102 s 12 KBi
#3
Correcto
0.246 s 12 KBi
#4
Correcto
0.389 s 54 KBi
#5
Correcto
0.478 s 26 KBi
#6
Correcto
0.677 s 57 KBi
#7
Correcto
0.676 s 48 KBi
#8
Correcto
0.6 s 57 KBi
Puntos totales: 100 / 100

Código

import java.util.HashMap;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.io.DataInputStream;
import java.io.FileInputStream;
 
public class Main{
    static class Reader{
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public Reader(){
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public Reader(String file_name) throws IOException{
            din = new DataInputStream(
                new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public String readLine() throws IOException{
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    if (cnt != 0)
                        break;
                    else
                        continue;
                }
                buf[cnt++] = (byte)c;
            }
            return new String(buf, 0, cnt);
        }
 
        public int nextInt() throws IOException{
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (neg)
                return -ret;
            return ret;
        }
 
        private void fillBuffer() throws IOException{
            bytesRead = din.read(buffer, bufferPointer = 0,
                                 BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }
 
        private byte read() throws IOException{
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
 
        public void close() throws IOException{
            if (din == null)
                return;
            din.close();
        }
    }

    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 {
        Reader fr = new Reader(); 
        Map<Integer, List<Integer>> byElems = new HashMap<>();
        int N = fr.nextInt();

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

        int Q = fr.nextInt();
        int L, R, X, left, right, j;
        String[] arr;
        L = R = X = left = right = 0;
        j = 3;
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i = 0; i < Q; i++){
            L = fr.nextInt();
            R = fr.nextInt();
            X = fr.nextInt();
            left = query(byElems.get(X), L - 1);
            right = query(byElems.get(X), R);
            bw.write((right - left + "\n"));
            j += 1;
        }
        bw.flush();
    }
}