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. 		Arrays.sort(contest, new Comparator<Integer[]>(){
  53. 			public int compare(Integer[] a, Integer[] b)
  54. 			{
  55. 				return Integer.compare(a[0], b[0]);
  56. 			}
  57. 		});
  58.  
  59. 		Arrays.sort(wormholeV);
  60. 		Arrays.sort(wormholew);
  61.  
  62. 		int min = -1;
  63. 		for (int i = 0; i < contest.length; i++)
  64. 		{
  65. 			int left = getLastSmaller(wormholeV, contest[i][0]);
  66. 			int right = getFirstLarger(wormholew, contest[i][1]);
  67. 			if (left == -1 || right == -1)
  68. 				continue;
  69.  
  70. 			int m = wormholew[right] - wormholeV[left] + 1;
  71. 			if (min == -1 || m < min)
  72. 			{
  73. 				min = m;
  74. 			}
  75. 		}
  76.  
  77. 		System.out.print(min);
  78. 	}
  79.  
  80. 	public static int getPos(int[]x, int element, int start, int end)
  81. 	{
  82. 		int mid = -1;
  83. 		while(start <= end)
  84. 		{
  85. 			mid = start + (end - start)/2;
  86. 			if (x[mid] == element)
  87. 				return mid;
  88.  
  89. 			if (element > x[mid])
  90. 				start = mid + 1;
  91. 			else
  92. 				end = mid - 1;
  93. 		}
  94. 		return mid;
  95. 	}
  96.  
  97. 	public static int getLastSmaller(int[]x, int element)
  98. 	{
  99. 		int m = getPos(x, element, 0, x.length - 1);
  100. 		if (m < 0)
  101. 			return m;
  102.  
  103. 		if (x[m] == element)
  104. 			return m;
  105.  
  106. 		return element < x[m] ? m - 1 : m;
  107. 	}
  108.  
  109. 	public static int getFirstLarger(int[]x, int element)
  110. 	{
  111. 		int m = getPos(x, element, 0, x.length - 1);
  112. 		if (m < 0)
  113.                         return 0;
  114. 		if (x[m] < element && m == x.length - 1)
  115. 			return -1;
  116. 		if (x[m] == element)
  117.                         return m;
  118.  
  119.                 return x[m] < element ? m + 1 : m;
  120. 	}
  121.  
  122. }
Success #stdin #stdout 0.04s 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/rBB7q5
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!