fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. import static java.lang.Integer.min;
  5.  
  6. /**
  7.  * Created by bugkiller on 27/01/18.
  8.  */
  9. class WarmHoles {
  10.         static class FastReader
  11.     {
  12.         BufferedReader br;
  13.         StringTokenizer st;
  14.  
  15.         public FastReader()
  16.         {
  17.             br = new BufferedReader(new
  18.                      InputStreamReader(System.in));
  19.         }
  20.  
  21.         String next()
  22.         {
  23.             while (st == null || !st.hasMoreElements())
  24.             {
  25.                 try
  26.                 {
  27.                     st = new StringTokenizer(br.readLine());
  28.                 }
  29.                 catch (IOException  e)
  30.                 {
  31.                     e.printStackTrace();
  32.                 }
  33.             }
  34.             return st.nextToken();
  35.         }
  36.  
  37.         int nextInt()
  38.         {
  39.             return Integer.parseInt(next());
  40.         }
  41.  
  42.         long nextLong()
  43.         {
  44.             return Long.parseLong(next());
  45.         }
  46.  
  47.         double nextDouble()
  48.         {
  49.             return Double.parseDouble(next());
  50.         }
  51.  
  52.         String nextLine()
  53.         {
  54.             String str = "";
  55.             try
  56.             {
  57.                 str = br.readLine();
  58.             }
  59.             catch (IOException e)
  60.             {
  61.                 e.printStackTrace();
  62.             }
  63.             return str;
  64.         }
  65.     }
  66.  
  67.     static int n,x,y;
  68.     static int s[] = new int[100000];
  69.     static int f[] = new int[100000];
  70.     static int v[] = new int[100000];
  71.     static int w[] = new int[100000];
  72.     static final int MAX = (int)1e8;
  73.     public static void main(String[] args) throws IOException {
  74.         FastReader in =new FastReader();
  75.         n = in.nextInt();
  76.         x = in.nextInt();
  77.         y = in.nextInt();
  78.         for (int i = 0; i < n; i++) {
  79.             s[i] = in.nextInt();
  80.             f[i] = in.nextInt();
  81.         }
  82.         for (int i = 0; i < x; i++) {
  83.             v[i] = in.nextInt();
  84.         }
  85.         for (int i = 0; i < y; i++) {
  86.             w[i] = in.nextInt();
  87.         }
  88.         Arrays.sort(v);
  89.         Arrays.sort(w);
  90.         System.out.println(solve());
  91.     }
  92.  
  93.     private static int solve(){
  94.         int totalTime = Integer.MAX_VALUE;
  95.         for (int i = 0; i < n; i++) {
  96.             int t1 = floor(s[i]);
  97.             int t2 = ceil(f[i]);
  98.             totalTime = min(totalTime, t2-t1+1);
  99.         }
  100.         return totalTime;
  101.     }
  102.  
  103.     public static int floor(int key) {
  104.         int start = 0, end = v.length-1;
  105.         while (start <= end) {
  106.             int mid = (start + end) / 2;
  107.             if (v[mid] <= key) {
  108.                 if(mid+1 == v.length || v[mid+1] > key)return v[mid];
  109.                 else{
  110.                     start = mid+1;
  111.                 }
  112.             } else {
  113.                 end = mid - 1;
  114.             }
  115.         }
  116.         if(v[start]>key)return -MAX;
  117.         return v[start];
  118.     }
  119.  
  120.     public static int ceil(int key) {
  121.         int start = 0, end = w.length-1;
  122.         while (start <= end) {
  123.             int mid = (start + end) / 2;
  124.             if (w[mid] >= key) {
  125.                 if(mid==0 || w[mid-1]<key)return w[mid];
  126.                 else end = mid-1;
  127.             } else {
  128.                 start = mid + 1;
  129.             }
  130.         }
  131.         if(w[end]<key)return MAX;
  132.         return w[end];
  133.     }
  134. }
Success #stdin #stdout 0.09s 4575232KB
comments (?)
stdin
copy 
3 4 2
15 21
5 10
7 25
4 14 25 2
13 21
stdout
copy 
8
https://ideone.com/viFI0u
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!