fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3. class Ideone{
  4.     static class Fast{
  5.         BufferedReader br;
  6.         StringTokenizer st;
  7.         BufferedWriter bw;
  8.         Fast() throws IOException{
  9.             br=new BufferedReader(new InputStreamReader(System.in));
  10.             bw=new BufferedWriter(new OutputStreamWriter(System.out));
  11.             st=new StringTokenizer(br.readLine());
  12.  
  13.         }
  14.         String next() throws IOException {
  15.             return (st.hasMoreElements()?st.nextToken():(st=new StringTokenizer(br.readLine())).nextToken());
  16.         }
  17.         int nextInt() throws IOException{
  18.             return Integer.parseInt(next());
  19.         }
  20.         long nextLong() throws IOException{
  21.             return Long.parseLong(next());
  22.         }
  23.         void print(Object o) throws IOException{
  24.             String s=String.valueOf(o);
  25.             bw.write(s);
  26.             bw.flush();
  27.         }
  28.     }
  29.     public static void main(String args[]) throws IOException {
  30.         Fast f=new Fast();
  31.         // int t=f.nextInt();
  32.         // while(t--!=0){
  33.             int n=f.nextInt();
  34.             HashMap<Integer,Integer> map=new HashMap<>();
  35.             for(int i=0;i<n;i++){
  36.                 int x=f.nextInt();
  37.                 map.put(x,map.containsKey(x)?map.get(x)+1:1);
  38.                 int y=f.nextInt();
  39.                 map.put(y+1,map.containsKey(y+1)?map.get(y+1)-1:-1);
  40.             }
  41.             int q=f.nextInt();
  42.             int qr[]=new int[q];
  43.             for(int i=0;i<q;i++){
  44.                 qr[i]=f.nextInt();
  45.             }
  46.             ArrayList<Integer> list=new ArrayList<>(map.keySet());
  47.             int max=list.get(list.size()-1);
  48.             int min=list.get(0);
  49.             int sum=0;
  50.             for(Map.Entry<Integer,Integer> entry:map.entrySet()){
  51.                 sum+=entry.getValue();
  52.                 entry.setValue(sum);
  53.             }
  54.  
  55.             for(int i=0;i<q;i++){
  56.                 if(qr[i]<=max && qr[i]>=min){
  57.                     if(list.contains(qr[i])){
  58.                         f.print(map.get(qr[i]) + "\n");
  59.                     }
  60.                     else{
  61.                         int start=0;
  62.                         int end=list.size()-1;
  63.                         int ans=-1;
  64.                         while(start<=end){
  65.                             int mid=(start+end)/2;
  66.                             if(list.get(mid)>=qr[i]){
  67.                                 end=mid-1;
  68.                             }
  69.                             else{
  70.                                 ans=mid;
  71.                                 start=mid+1;
  72.                             }
  73.                         }
  74.                         f.print(map.get(list.get(ans)) + "\n");
  75.                 }
  76.             }
  77.                 else{
  78.                     f.print(0 + "\n");
  79.                 }
  80.             }
  81. }
  82. }
  83.  
Success #stdin #stdout 0.12s 50280KB
comments (?)
stdin
copy 
4
1 3
1 6
3 5
5 9
4
3
6
4
2
stdout
copy 
3
2
2
2
https://ideone.com/sprlcC
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!