daily pastebin goal
25%
SHARE
TWEET

Samara 2018 C

a guest Mar 18th, 2018 182 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class C implements Runnable{
  5.     public static void main (String[] args) {new Thread(null, new C(), "_cf", 1 << 28).start();}
  6.  
  7.     public void run() {
  8.         FastScanner fs = new FastScanner();
  9.         PrintWriter out = new PrintWriter(System.out);
  10.         System.err.println("Go!");
  11.  
  12.         int n = fs.nextInt();
  13.         Range[] a = new Range[2*n];
  14.         for(int i = 0; i < n; i++) {
  15.             int s = fs.nextInt(), e = fs.nextInt();
  16.             a[i] = new Range(s, e, false);
  17.             a[i + n] = new Range(s, e, true);
  18.         }
  19.         Arrays.sort(a);
  20.         TreeSet<Integer> set = new TreeSet<>();
  21.         for(Range r : a) {
  22.             if(r.end == false) continue;
  23.             Integer hi = set.ceiling(r.s);
  24.             if(hi == null || hi > r.e) {
  25.                 set.add(r.e);
  26.             }
  27.         }
  28.        
  29.         out.println(set.size());
  30.         while(!set.isEmpty()) {
  31.             out.print(set.pollFirst());
  32.             if(set.isEmpty()) out.println();
  33.             else out.print(" ");
  34.         }
  35.        
  36.  
  37.         out.close();
  38.     }
  39.    
  40.     class Range implements Comparable<Range> {
  41.         int s, e, use;
  42.         boolean end;
  43.         Range (int a, int b, boolean f) {
  44.             s = a; e = b;
  45.             if(f) use = e;
  46.             else use = s;
  47.             end = f;
  48.         }
  49.         public int compareTo(Range o) {
  50.             if(use == o.use) {
  51.                 return Boolean.compare(end, o.end);
  52.             }
  53.             return Integer.compare(use, o.use);
  54.         }
  55.     }
  56.  
  57.     void sort (int[] a) {
  58.         int n = a.length;
  59.         for(int i = 0; i < 50; i++) {
  60.             Random r = new Random();
  61.             int x = r.nextInt(n), y = r.nextInt(n);
  62.             int temp = a[x];
  63.             a[x] = a[y];
  64.             a[y] = temp;
  65.         }
  66.         Arrays.sort(a);
  67.     }
  68.  
  69.     class FastScanner {
  70.         BufferedReader br;
  71.         StringTokenizer st;
  72.         public FastScanner() {
  73.             try {
  74.                 br = new BufferedReader(new InputStreamReader(System.in));
  75.                 //                br = new BufferedReader(new FileReader("testdata.out"));
  76.                 st = new StringTokenizer("");
  77.             } catch (Exception e){e.printStackTrace();}
  78.         }
  79.         public String next() {
  80.             if (st.hasMoreTokens()) return st.nextToken();
  81.             try {st = new StringTokenizer(br.readLine());}
  82.             catch (Exception e) {e.printStackTrace();}
  83.             return st.nextToken();
  84.         }
  85.         public int nextInt() {return Integer.parseInt(next());}
  86.         public long nextLong() {return Long.parseLong(next());}
  87.         public double nextDouble() {return Double.parseDouble(next());}
  88.  
  89.         public String nextLine() {
  90.             String line = "";
  91.             try {line = br.readLine();}
  92.             catch (Exception e) {e.printStackTrace();}
  93.             return line;
  94.         }
  95.         public Integer[] nextIntegerArray(int n) {
  96.             Integer[] a = new Integer[n];
  97.             for(int i = 0; i < n; i++) a[i] = nextInt();
  98.             return a;
  99.         }
  100.         public int[] nextIntArray(int n) {
  101.             int[] a = new int[n];
  102.             for(int i = 0; i < n; i++) a[i] = nextInt();
  103.             return a;
  104.         }
  105.         public char[] nextCharArray() {return nextLine().toCharArray();}
  106.     }
  107.  
  108. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top