fork download
copy 
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. class Main
  5. {
  6.  
  7. 	public static void main(String args[]) throws Exception
  8. 	{
  9. /*
  10. 		int[] t = {2, 4, 6, 8, 10};
  11.                 System.out.println(getLastSmaller(t, 300));
  12. 		System.out.println(getLastSmaller(t, 0));
  13.                 System.out.println(getLastSmaller(t, 7));
  14. 		System.out.println(getFirstLarger(t, 300));
  15.                 System.out.println(getFirstLarger(t, 0));
  16.                 System.out.println(getFirstLarger(t, 7));
  17. 		int[] t2 = {1, 3, 5, 7};
  18. 		System.out.println(getLastSmaller(t2, 300));
  19.                 System.out.println(getLastSmaller(t2, 0));
  20.                 System.out.println(getLastSmaller(t2, 6));
  21.                 System.out.println(getFirstLarger(t2, 300));
  22.                 System.out.println(getFirstLarger(t2, 0));
  23.                 System.out.println(getFirstLarger(t2, 6));	
  24. */	
  25. /*		BufferedReader b = new BufferedReader(new InputStreamReader(System.in));
  26. 		StringTokenizer st = new StringTokenizer(b.readLine());
  27. 		int n = Integer.parseInt(st.nextToken());
  28. 		int x = Integer.parseInt(st.nextToken());
  29. 		int y = Integer.parseInt(st.nextToken());
  30.  
  31. 		Integer[][] contest = new Integer[n][2];
  32. 		int[] wormholeV = new int[x];
  33. 		int[] wormholew = new int[y];
  34. 		for (int i = 0; i < n; i++)
  35.                 {
  36. 			String[] splt = b.readLine().split("\\s");
  37. 			contest[i][0] = Integer.parseInt(splt[0].trim());
  38. 			contest[i][1] = Integer.parseInt(splt[1].trim());
  39. 		}
  40.  
  41. 		String[] V = b.readLine().split("\\s");
  42. 		for (int i = 0; i < x; i++)
  43. 		{
  44. 			wormholeV[i] = Integer.parseInt(V[i].trim());
  45. 		}
  46. 		String[] W = b.readLine().split("\\s");
  47. 		for (int i = 0; i < y; i++)
  48. 		{
  49. 			wormholew[i] = Integer.parseInt(W[i].trim());
  50. 		}
  51. */
  52. 		Scanner sc = new Scanner(System.in);
  53. 		int n = sc.nextInt();
  54.                 int x = sc.nextInt();
  55.                 int y = sc.nextInt();
  56.  
  57. 		Integer[][] contest = new Integer[n][2];
  58.                 int[] wormholeV = new int[x];
  59.                 int[] wormholew = new int[y];
  60.                 for (int i = 0; i < n; i++)
  61.                 {
  62. 			contest[i][0] = sc.nextInt();
  63. 			contest[i][1] = sc.nextInt();
  64. 		}		
  65.  
  66. 		for (int i = 0; i < x; i++)
  67.                 {
  68.                         wormholeV[i] = sc.nextInt();
  69.                 }
  70.  
  71.                 for (int i = 0; i < y; i++)
  72.                 {
  73.                         wormholew[i] = sc.nextInt();
  74.                 }
  75.  
  76. 		Arrays.sort(contest, new Comparator<Integer[]>(){
  77. 			public int compare(Integer[] a, Integer[] b)
  78. 			{
  79. 				return Integer.compare(a[0], b[0]);
  80. 			}
  81. 		});
  82.  
  83. 		Arrays.sort(wormholeV);
  84. 		Arrays.sort(wormholew);
  85.  
  86. 		int min = -1;
  87. 		for (int i = 0; i < contest.length; i++)
  88. 		{
  89. 			int left = getLastSmaller(wormholeV, contest[i][0]);
  90. 			int right = getFirstLarger(wormholew, contest[i][1]);
  91. 			if (left == -1 || right == -1)
  92. 				continue;
  93.  
  94. 			int m = wormholew[right] - wormholeV[left] + 1;
  95. 			if (min == -1 || m < min)
  96. 			{
  97. 				min = m;
  98. 			}
  99. 		}
  100.  
  101. 		System.out.print(min);
  102. 	}
  103.  
  104. 	public static int getPos(int[]x, int element, int start, int end)
  105. 	{
  106. 		int mid = -1;
  107. 		while(start <= end)
  108. 		{
  109. 			mid = start + (end - start)/2;
  110. 			if (x[mid] == element)
  111. 				return mid;
  112.  
  113. 			if (element > x[mid])
  114. 				start = mid + 1;
  115. 			else
  116. 				end = mid - 1;
  117. 		}
  118. 		return mid;
  119. 	}
  120.  
  121. 	public static int getLastSmaller(int[]x, int element)
  122. 	{
  123. 		int m = getPos(x, element, 0, x.length - 1);
  124. 		if (m < 0)
  125. 			return m;
  126.  
  127. 		if (x[m] == element)
  128. 			return m;
  129.  
  130. 		return element < x[m] ? m - 1 : m;
  131. 	}
  132.  
  133. 	public static int getFirstLarger(int[]x, int element)
  134. 	{
  135. 		int m = getPos(x, element, 0, x.length - 1);
  136. 		if (m < 0)
  137.                         return 0;
  138. 		if (x[m] < element && m == x.length - 1)
  139. 			return -1;
  140. 		if (x[m] == element)
  141.                         return m;
  142.  
  143.                 return x[m] < element ? m + 1 : m;
  144. 	}
  145.  
  146. }
Success #stdin #stdout 0.06s 4386816KB
comments (?)
stdin
copy 
3 4 2
15 21
5 10
7 25
4 14 25 2
13 21
stdout
copy 
8
https://ideone.com/yiqfzn
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!