fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. class Ideone {
  5.     static class Fast {
  6.         BufferedReader br;
  7.         StringTokenizer st;
  8.         BufferedWriter bw;
  9.  
  10.         Fast() throws IOException {
  11.             br = new BufferedReader(new InputStreamReader(System.in));
  12.             bw = new BufferedWriter(new OutputStreamWriter(System.out));
  13.             st = new StringTokenizer(br.readLine());
  14.  
  15.         }
  16.  
  17.         String next() throws IOException {
  18.             return (st.hasMoreElements() ? st.nextToken() : (st = new StringTokenizer(br.readLine())).nextToken());
  19.         }
  20.  
  21.         int nextInt() throws IOException {
  22.             return Integer.parseInt(next());
  23.         }
  24.  
  25.         long nextLong() throws IOException {
  26.             return Long.parseLong(next());
  27.         }
  28.  
  29.         void print(Object o) throws IOException {
  30.             String s = String.valueOf(o);
  31.             bw.write(s);
  32.             bw.flush();
  33.         }
  34.     }
  35.  
  36.     public static void main(String args[]) throws IOException {
  37.         Fast f = new Fast();
  38.         int t = f.nextInt();
  39.         while (t-- != 0) {
  40.  
  41.             int n = f.nextInt();
  42.             HashMap<Integer, Integer> map = new HashMap<>();
  43.             for (int i = 0; i < n; i++) {
  44.                 int x = f.nextInt();
  45.                 map.put(x, map.containsKey(x) ? map.get(x) + 1 : 1);
  46.                 int y = f.nextInt();
  47.                 map.put(y + 1, map.containsKey(y + 1) ? map.get(y + 1) - 1 : -1);
  48.             }
  49.             // created an map of l and r+1 with respective values . . . .
  50.  
  51.             int q = f.nextInt();
  52.             //input queries
  53.             int qr[] = new int[q];
  54.             for (int i = 0; i < q; i++) {
  55.                 qr[i] = f.nextInt();
  56.             }
  57.  
  58.             //to check the missing values in between an arraylist
  59.             ArrayList<Integer> list = new ArrayList<>(map.keySet());
  60.             int max = list.get(list.size() - 1);
  61.             int min = list.get(0);
  62.             int sum = 0;
  63.             //to create a prefix map sortof thing
  64.             for (Map.Entry<Integer, Integer> entry : map.entrySet()) 
  65.             {
  66.                 sum += entry.getValue();
  67.                 entry.setValue(sum);
  68.             }
  69.  
  70.             for (int i = 0; i < q; i++) {
  71.             	//every query in q[] if is >=min of arraylist and <=max of arraylist 
  72.                 if (qr[i] <= max && qr[i]>=min ) {
  73.                     if (list.contains(qr[i])) {
  74.                         f.print(map.get(qr[i]) + "\n");    //if we have it in the list we will print its corresponding value else we'll have to search for its corresponding value in prefix map which is just less than it 
  75.                     } else {
  76.                         int start = 0;
  77.                         int end = list.size() - 1;
  78.                         int ans = -1;
  79.                         while (start <= end) {
  80.                             int mid = (start + end) / 2;
  81.                             if (list.get(mid) >= qr[i]) {
  82.                                 end = mid - 1;
  83.                             } else {
  84.                                 ans = mid;
  85.                                 start = mid + 1;
  86.                             }
  87.                         }
  88.                         f.print(map.get(list.get(ans)) + "\n");
  89.                     }
  90.                 }
  91.                 else{ //if value is outside the range of min and max // not produced by manufactures 
  92.                 	f.print(0 + "\n");
  93.                 }
  94.             }
  95.         }
  96.     }
  97.  
  98. }
Success #stdin #stdout 0.13s 52376KB
comments (?)
stdin
copy 
1
4
1 3
1 6
3 5
5 9
4
3
8
6
10
stdout
copy 
3
1
2
0
https://ideone.com/uziqau
language:
Java (HotSpot 12)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!