fork download
copy 
  1.     import java.util.*;
  2.     import java.io.*;
  3.     //Solution Credits: Taranpreet Singh
  4.     class Editorial{
  5.         //SOLUTION BEGIN
  6.         void solve(int TC) throws Exception{
  7.             //Offline Solution - O(NlogN+MlogM)
  8.             int n = ni(), m = ni();
  9.             long[][] inte = new long[n][];
  10.             for(int i = 0; i< n; i++)inte[i] = new long[]{nl(), nl()};
  11.             //Sorted intervals by right end.
  12.             Arrays.sort(inte, (long[] l0, long[] l1) -> Long.compare(l0[1], l1[1]));
  13.             long[][] qq = new long[m][2];
  14.             long[] ans = new long[m];
  15.             for(int i = 0; i< m; i++){
  16.                 qq[i][0] = i;
  17.                 qq[i][1] = nl();
  18.             }
  19.             //Sorted queries by their time.
  20.             Arrays.sort(qq, (long[] l0, long[] l1) -> Long.compare(l0[1], l1[1]));
  21.             int query = 0;
  22.             for(int interval = 0;interval<n; interval++){
  23.                 while(query<m && qq[query][1]<inte[interval][1]){
  24.                     if(qq[query][1]< inte[interval][0])//If query doesn't belong to interval.
  25.                         ans[(int)qq[query][0]] = inte[interval][0]-qq[query][1];
  26.                     query++;
  27.                 }
  28.             }
  29.             //Handling those query times, which will not served food.
  30.             while(query<m)ans[(int)qq[query++][0]] = -1;
  31.             //Printing answer
  32.             for(long l:ans)pn(l);
  33.         }
  34.         //SOLUTION ENDS
  35.         boolean multipleTC = true;
  36.         FastReader in;PrintWriter out;
  37.         void run() throws Exception{
  38.             in = new FastReader();
  39.             out = new PrintWriter(System.out);
  40.             for(int i = 1, T = (multipleTC)?ni():1; i<= T; i++)solve(i);
  41.             out.flush();
  42.             out.close();
  43.         }
  44.         public static void main(String[] args) throws Exception{
  45.             new Editorial().run();
  46.         }
  47.         void p(Object o){out.print(o);}
  48.         void pn(Object o){out.println(o);}
  49.         void pni(Object o){out.println(o);out.flush();}
  50.         String n(){return in.next();}
  51.         String nln(){return in.nextLine();}
  52.         int ni(){return Integer.parseInt(in.next());}
  53.         long nl(){return Long.parseLong(in.next());}
  54.         double nd(){return Double.parseDouble(in.next());}
  55.         class FastReader{
  56.             BufferedReader br;
  57.             StringTokenizer st;
  58.             public FastReader(){
  59.                 br = new BufferedReader(new InputStreamReader(System.in));
  60.             }
  61.  
  62.             public FastReader(String s) throws Exception{
  63.                 br = new BufferedReader(new FileReader(s));
  64.             }
  65.  
  66.             String next(){
  67.                 while (st == null || !st.hasMoreElements()){
  68.                     try{
  69.                         st = new StringTokenizer(br.readLine());
  70.                     }catch (IOException  e){
  71.                         e.printStackTrace();
  72.                     }
  73.                 }
  74.                 return st.nextToken();
  75.             }
  76.  
  77.             String nextLine(){
  78.                 String str = "";
  79.                 try{    
  80.                     str = br.readLine();
  81.                 }catch (IOException e){
  82.                     e.printStackTrace();
  83.                 }   
  84.                 return str;
  85.             }
  86.         }
  87.     }
Success #stdin #stdout 0.14s 2184192KB
comments (?)
stdin
copy 
1
4 5
5 7
9 10
2 3
20 30
5
6
7
35
1
stdout
copy 
0
0
2
-1
1
https://ideone.com/Ls5gd5
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
secret

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!