fork(1) download
copy 
  1. import java.io.*;
  2. import java.math.BigInteger;
  3. import java.util.*;
  4. import java.util.regex.Matcher;
  5. import java.util.regex.Pattern;
  6.  
  7. import javax.net.ssl.SSLContext;
  8.  
  9. public class Main
  10. {	
  11.    static HashMap<Integer,Integer> index;static int g=0; static int l=0;
  12.  
  13.    public static int lower_bound(int start,int end,int a[],int key)
  14.    {
  15. 	   if(start>end) return start;
  16. 	   int mid=(start+end)>>1;
  17.  
  18. 	   if(a[mid]==key) return mid;
  19.  
  20. 	   if(key<a[mid]) return lower_bound(start,mid-1,a,key);
  21. 	   else return lower_bound(mid+1,end,a,key);  
  22.    }
  23.  
  24.    public static void main(String[] args) throws java.lang.Exception
  25.    {	  	 
  26.  
  27. 	     fast s = new fast();
  28. 	     PrintWriter out=new PrintWriter(System.out);
  29. 	     StringBuilder final_ans = new StringBuilder();
  30.  
  31. 	     int t=s.nextInt();
  32.  
  33. 	     while(t!=0)
  34. 	     {
  35. 	    	 int n=s.nextInt();
  36. 	    	 int st=s.nextInt();
  37. 	    	 index=new HashMap<Integer,Integer>();
  38.  
  39. 	    	 int a[]=new int[n];
  40. 	    	 int b[]=new int[st];    	 
  41. 	    	 int temp[]=new int[n];
  42.  
  43. 	    	 for(int i=0;i<n;i++) {a[i]=s.nextInt();temp[i]=a[i];index.put(a[i], i);}
  44. 	    	 for(int i=0;i<st;i++) b[i]=s.nextInt();
  45.  
  46.     		 Arrays.sort(temp);
  47. 	    	 for(int i=0;i<st;i++)
  48. 	    	 {
  49. 	    		 l=0; g=0;
  50. 	    		 int pos=index.get(b[i]);
  51.  
  52. 	    		 int low=0; int high=n-1;
  53.  
  54. 	    		 while(low<=high)
  55. 	    		 {
  56. 	    			 int mid=(low+high)>>1;
  57.  
  58. 	    		     if(mid==pos) break;
  59.  
  60. 	    		     if(mid<pos)
  61. 	    		     {
  62. 	    		    	 if(a[mid]>b[i]) g++;
  63. 	    		    	 low=mid+1;
  64. 	    		     }
  65. 	    		     else if(mid>pos)
  66. 	    		     {
  67. 	    		    	 if(a[mid]<b[i]) l++;
  68. 	    		    	 high=mid-1;
  69. 	    		     }	    		 
  70. 	    		 }
  71.  
  72. 	    		 int lb=lower_bound(0,n-1,temp,b[i]);
  73. 	    		 int gb=n-1-lb;
  74.  
  75. 	    		 if(l==g) System.out.println(l);
  76. 	    		 else if(l>g)
  77. 	    		 {
  78. 	    			 if(gb<l) System.out.println("-1");
  79. 	    			 else System.out.println(l);
  80.  
  81. 	    		 }
  82. 	    		 else
  83. 	    		 {
  84. 	    			 if(lb<g) System.out.println("-1");
  85. 	    			 else System.out.println(g);
  86. 	    		 }	    	   
  87. 	    	 }
  88.  
  89. 	    	 t--;
  90. 	     }
  91.  
  92.    }
  93.  
  94.    static class fast {
  95. 		private InputStream i;
  96. 		private byte[] buf = new byte[1024];
  97. 		private int curChar;
  98. 		private int numChars;
  99.  
  100. 		public int gcd(int a,int b)
  101. 		{
  102. 			if(a==0) return b;
  103. 			return gcd(b%a,b);
  104. 		}
  105. 		public fast() {
  106. 			this(System.in);
  107. 		}
  108. 		public fast(InputStream is) {
  109. 			i = is;
  110. 		}
  111. 		public int read() {
  112. 			if (numChars == -1)
  113. 				throw new InputMismatchException();
  114. 			if (curChar >= numChars) {
  115. 				curChar = 0;
  116. 				try {
  117. 					numChars = i.read(buf);
  118. 				} catch (IOException e) {
  119. 					throw new InputMismatchException();
  120. 				}
  121. 				if (numChars <= 0)
  122. 					return -1;
  123. 			}
  124. 			return buf[curChar++];
  125. 		}
  126. 		public String nextLine() {
  127. 			int c = read();
  128. 			while (isSpaceChar(c))
  129. 				c = read();
  130. 			StringBuilder res = new StringBuilder();
  131. 			do {
  132. 				res.appendCodePoint(c);
  133. 				c = read();
  134. 			} while (!isEndOfLine(c));
  135. 			return res.toString();
  136. 		}
  137. 		public String nextString() {
  138.      		int c = read();
  139. 			while (isSpaceChar(c))
  140. 				c = read();
  141. 			StringBuilder res = new StringBuilder();
  142. 			do {
  143. 				res.appendCodePoint(c);
  144. 				c = read();
  145. 			} while (!isSpaceChar(c));
  146. 			return res.toString();
  147. 		}
  148. 		public long nextLong() {
  149. 			int c = read();
  150. 			while (isSpaceChar(c))
  151. 				c = read();
  152. 			int sgn = 1;
  153. 			if (c == '-') {
  154. 				sgn = -1;
  155. 				c = read();
  156. 			}
  157. 			long res = 0;
  158. 			do {
  159. 				if (c < '0' || c > '9')
  160. 					throw new InputMismatchException();
  161. 				res *= 10;
  162. 				res += c - '0';
  163. 				c = read();
  164. 			} while (!isSpaceChar(c));
  165. 			return res * sgn;
  166. 		}
  167. 		public int nextInt() {
  168. 			int c = read();
  169. 			while (isSpaceChar(c))
  170. 				c = read();
  171. 			int sgn = 1;
  172. 			if (c == '-') {
  173. 				sgn = -1;
  174. 				c = read();
  175. 			}
  176. 			int res = 0;
  177. 			do {
  178. 				if (c < '0' || c > '9')
  179. 					throw new InputMismatchException();
  180. 				res *= 10;
  181. 				res += c - '0';
  182. 				c = read();
  183. 			} while (!isSpaceChar(c));
  184. 			return res * sgn;
  185. 		}
  186. 		public boolean isSpaceChar(int c) {
  187. 			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  188. 		}
  189. 		public boolean isEndOfLine(int c) {
  190. 			return c == '\n' || c == '\r' || c == -1;
  191. 		}
  192.  
  193. 	}	
  194. }
  195.  
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202.  
Success #stdin #stdout 0.05s 27456KB
comments (?)
stdin
copy 
1
7 7
3 1 6 7 2 5 4
1
2
3
4
5
6
7
stdout
copy 
0
1
1
2
1
0
0
https://ideone.com/VnwXtb
language:
Java (HotSpot 12)
created:
6 years 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!