Facebook
From Md Ahsanul Haque, 1 Month ago, written in Java.
Embed
Download Paste or View Raw
Hits: 49
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.StringTokenizer;
  5.  
  6. public class lightoj1088 {
  7.    
  8.     static int binarysearchlower(int[] arr, int key){
  9.        int begin = 0;
  10.         int end = arr.length - 1;
  11.         int index = -1;
  12.         while(begin<=end){
  13.             int mid = (begin+end)/2;
  14.             if(key <= arr[mid]){
  15.                 index = mid;
  16.                 end = mid - 1;
  17.             }else if(key>arr[mid]){
  18.                 begin = mid + 1;
  19.             }else{
  20.                 end = mid - 1;
  21.             }
  22.         }
  23.         return index;
  24.        
  25.    }
  26.    
  27.    static int binarysearchupper(int[] arr, int key){
  28.        int begin = 0;
  29.         int end = arr.length - 1;
  30.         int index = -1;
  31.         while(begin<=end){
  32.             int mid = (begin+end)/2;
  33.             if(key >= arr[mid]){
  34.                 index = mid;
  35.                 begin = mid + 1;
  36.             }else if(key>arr[mid]){
  37.                 begin = mid + 1;
  38.             }else{
  39.                 end = mid - 1;
  40.             }
  41.         }
  42.         return index;
  43.        
  44.    }
  45.    
  46.    static class FastReader {
  47.         BufferedReader br;
  48.         StringTokenizer st;
  49.  
  50.         public FastReader()
  51.         {
  52.             br = new BufferedReader(
  53.                 new InputStreamReader(System.in));
  54.         }
  55.  
  56.         String next()
  57.         {
  58.             while (st == null || !st.hasMoreElements()) {
  59.                 try {
  60.                     st = new StringTokenizer(br.readLine());
  61.                 }
  62.                 catch (IOException e) {
  63.                     e.printStackTrace();
  64.                 }
  65.             }
  66.             return st.nextToken();
  67.         }
  68.  
  69.         int nextInt() { return Integer.parseInt(next()); }
  70.  
  71.         long nextLong() { return Long.parseLong(next()); }
  72.  
  73.         double nextDouble()
  74.         {
  75.             return Double.parseDouble(next());
  76.         }
  77.  
  78.         String nextLine()
  79.         {
  80.             String str = "";
  81.             try {
  82.                 if(st.hasMoreTokens()){
  83.                     str = st.nextToken("\n");
  84.                 }
  85.                 else{
  86.                     str = br.readLine();
  87.                 }
  88.             }
  89.             catch (IOException e) {
  90.                 e.printStackTrace();
  91.             }
  92.             return str;
  93.         }
  94.     }
  95.  
  96.    
  97.    public static void main(String[] args) throws IOException{
  98.         FastReader s = new FastReader();
  99.        
  100.         int t = s.nextInt();
  101.         int up, low, lowindex, upindex;
  102.         for(int j=1;j<=t;j++){
  103.             int n = s.nextInt();
  104.             int q = s.nextInt();
  105.             int[] arr = new int[n];
  106.             for(int i=0;i<n;i++){
  107.                arr[i] = s.nextInt();
  108.             }
  109.             System.out.println("Case "+j+":");
  110.             for(int i=0;i<q;i++){
  111.                 low = s.nextInt();
  112.                 up = s.nextInt();
  113.                
  114.                 lowindex = binarysearchlower(arr,low);
  115.                 upindex = binarysearchupper(arr,up);
  116.                
  117. //              System.out.println("Low index: "+lowindex+" Up index: "+upindex);
  118.                 System.out.println((upindex-lowindex)+1);
  119.                
  120.             }
  121.            
  122.         }
  123. }
  124.