Advertisement
Guest User

C - Aerotaxi

a guest
Jun 22nd, 2015
407
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 7.08 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.ArrayList;
  3. import java.util.Collections;
  4. import java.util.List;
  5. import java.util.StringTokenizer;
  6.  
  7. public class C_AA_NIGHT {
  8.  
  9.     final boolean ONLINE_JUDGE = true;
  10.     BufferedReader in;
  11.     PrintWriter out;
  12.     StringTokenizer tok = new StringTokenizer("");
  13.  
  14.     class Interval {
  15.         int hall;
  16.         int from;
  17.         int to;
  18.         int start;
  19.         Interval prev;
  20.  
  21.         public Interval(int hall, int from, int to, int start) {
  22.             this.hall = hall;
  23.             this.from = from;
  24.             this.to = to;
  25.             this.start = start;
  26.         }
  27.  
  28.  
  29.         public Interval(int hall, int from, int to, int start, Interval prev) {
  30.             this.hall = hall;
  31.             this.from = from;
  32.             this.to = to;
  33.             this.start = start;
  34.             this.prev = prev;
  35.         }
  36.     }
  37.  
  38.     void solve() throws IOException {
  39.         int n = readInt();
  40.         int t = readInt();
  41.         Interval res = null;
  42.         Interval[][] intervals = new Interval[n][];
  43.         int[][] x = new int[n][];
  44.         for(int i = 0; i < n; i++) {
  45.             int curNum = readInt();
  46.             x[i] = new int[2 * curNum + 2];
  47.             x[i][0] = 0;
  48.             x[i][x[i].length-1] = 2 * 1000 * 1000 * 1000;
  49.             for(int j = 1; j < x[i].length-1; j++) {
  50.                 x[i][j] = readInt();
  51.             }
  52.         }
  53.  
  54.         for(int i = 0; i < n; i++) {
  55.             List<Interval> curIntervals = new ArrayList<Interval>();
  56.             if(i == 0) {
  57.                 for(int j = 0; j < x[i].length / 2; j++) {
  58.                     int from = x[i][j*2];
  59.                     int to = x[i][j*2+1];
  60.                     if(from == to) continue;
  61.                     curIntervals.add(new Interval(i, from, to, from));
  62.                 }
  63.                 intervals[i] = new Interval[curIntervals.size()];
  64.                 for(int j = 0; j < curIntervals.size(); j++) {
  65.                     Interval interval = curIntervals.get(j);
  66.                     intervals[i][j] = interval;
  67.                     interval = curIntervals.get(j);
  68.                     int dist = interval.to - interval.start;
  69.                     if(dist >= t) {
  70.                         if(res == null || res.start > interval.start) {
  71.                             res = interval;
  72.                         }
  73.                     }
  74.                 }
  75.                 continue;
  76.             }
  77.             Interval[] prev = intervals[i-1];
  78.             int pointer = 0;
  79.             for(int j = 0; j < x[i].length / 2; j++) {
  80.                 int from = x[i][j*2];
  81.                 int to = x[i][j*2+1];
  82.                 if(from == to) continue;
  83.                 List<Interval> now = new ArrayList<Interval>();
  84.                 now.add(new Interval(i, from, from, from, null));
  85.                 while (pointer < prev.length) {
  86.                     Interval prevInterval = prev[pointer];
  87.                     if(prevInterval.to < from) {
  88.                         pointer++;
  89.                         continue;
  90.                     }
  91.                     if(prevInterval.from + 1 >= to) {
  92.                         break;
  93.                     }
  94.                     int nf = prevInterval.from + 1;
  95.                     int nt = prevInterval.to + 1;
  96.                     if(nf < from) {
  97.                         nf = from;
  98.                     }
  99.                     if(nt > to) {
  100.                         nt = to;
  101.                     }
  102.                     now.add(new Interval(i, nf, nt, prevInterval.start, prevInterval));
  103.                     if(prevInterval.to <= to) pointer++;
  104.                     else break;
  105.                 }
  106.                 Interval prevInterval = now.get(0);
  107.                 for(int k = 1; k < now.size(); k++) {
  108.                     Interval curInterval = now.get(k);
  109.                     if(prevInterval.start <= curInterval.start) {
  110.                         prevInterval.to = curInterval.to;
  111.                     } else {
  112.                         prevInterval.to = curInterval.from;
  113.                         if(prevInterval.from != prevInterval.to) curIntervals.add(prevInterval);
  114.                         prevInterval = curInterval;
  115.                     }
  116.                 }
  117.                 prevInterval.to = to;
  118.                 curIntervals.add(prevInterval);
  119.             }
  120.             intervals[i] = new Interval[curIntervals.size()];
  121.             for(int j = 0; j < curIntervals.size(); j++) {
  122.                 Interval interval = curIntervals.get(j);
  123.                 intervals[i][j] = interval;
  124.                 interval = curIntervals.get(j);
  125.                 int dist = interval.to - interval.start;
  126.                 if(dist >= t) {
  127.                     if(res == null || res.start > interval.start) {
  128.                         res = interval;
  129.                     }
  130.                 }
  131.             }
  132.         }
  133.  
  134.         out.println(res.start);
  135.         List<Integer> changes = new ArrayList<Integer>();
  136.         while(true) {
  137.             if(res.prev == null) {
  138.                 break;
  139.             }
  140.             Interval prev = res.prev;
  141.             int time = res.from;
  142.             if(prev.from > time) {
  143.                 time = prev.from+1;
  144.             }
  145.             changes.add(time);
  146.             res = prev;
  147.         }
  148.  
  149.         out.println((res.hall+1) + " " + changes.size());
  150.         Collections.reverse(changes);
  151.         for(int i: changes) {
  152.             out.print(i + " ");
  153.         }
  154.     }
  155.  
  156.  
  157.     void init() throws FileNotFoundException {
  158.         if (ONLINE_JUDGE) {
  159.             in = new BufferedReader(new InputStreamReader(System.in));
  160.             out = new PrintWriter(System.out);
  161.         } else {
  162.             in = new BufferedReader(new FileReader("input.txt"));
  163.             out = new PrintWriter("output.txt");
  164.         }
  165.     }
  166.  
  167.     String readString() throws IOException {
  168.         while (!tok.hasMoreTokens()) {
  169.             tok = new StringTokenizer(in.readLine());
  170.         }
  171.         return tok.nextToken();
  172.     }
  173.  
  174.     int readInt() throws IOException {
  175.         return Integer.parseInt(readString());
  176.     }
  177.  
  178.     long readLong() throws IOException {
  179.         return Long.parseLong(readString());
  180.     }
  181.  
  182.     double readDouble() throws IOException {
  183.         return Double.parseDouble(readString());
  184.     }
  185.  
  186.     int[] readArr(int n) throws IOException {
  187.         int[] res = new int[n];
  188.         for (int i = 0; i < n; i++) {
  189.             res[i] = readInt();
  190.         }
  191.         return res;
  192.     }
  193.  
  194.     long[] readArrL(int n) throws IOException {
  195.         long[] res = new long[n];
  196.         for (int i = 0; i < n; i++) {
  197.             res[i] = readLong();
  198.         }
  199.         return res;
  200.     }
  201.  
  202.     public static void main(String[] args) {
  203.         new C_AA_NIGHT().run();
  204.     }
  205.  
  206.     public void run() {
  207.         try {
  208.             long t1 = System.currentTimeMillis();
  209.             init();
  210.             solve();
  211.             out.close();
  212.             long t2 = System.currentTimeMillis();
  213.             System.err.println("Time = " + (t2 - t1));
  214.         } catch (Exception e) {
  215.             e.printStackTrace(System.err);
  216.             System.exit(-1);
  217.         }
  218.     }
  219. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement