Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.ArrayList;
- import java.util.Collections;
- import java.util.List;
- import java.util.StringTokenizer;
- public class C_AA_NIGHT {
- final boolean ONLINE_JUDGE = true;
- BufferedReader in;
- PrintWriter out;
- StringTokenizer tok = new StringTokenizer("");
- class Interval {
- int hall;
- int from;
- int to;
- int start;
- Interval prev;
- public Interval(int hall, int from, int to, int start) {
- this.hall = hall;
- this.from = from;
- this.to = to;
- this.start = start;
- }
- public Interval(int hall, int from, int to, int start, Interval prev) {
- this.hall = hall;
- this.from = from;
- this.to = to;
- this.start = start;
- this.prev = prev;
- }
- }
- void solve() throws IOException {
- int n = readInt();
- int t = readInt();
- Interval res = null;
- Interval[][] intervals = new Interval[n][];
- int[][] x = new int[n][];
- for(int i = 0; i < n; i++) {
- int curNum = readInt();
- x[i] = new int[2 * curNum + 2];
- x[i][0] = 0;
- x[i][x[i].length-1] = 2 * 1000 * 1000 * 1000;
- for(int j = 1; j < x[i].length-1; j++) {
- x[i][j] = readInt();
- }
- }
- for(int i = 0; i < n; i++) {
- List<Interval> curIntervals = new ArrayList<Interval>();
- if(i == 0) {
- for(int j = 0; j < x[i].length / 2; j++) {
- int from = x[i][j*2];
- int to = x[i][j*2+1];
- if(from == to) continue;
- curIntervals.add(new Interval(i, from, to, from));
- }
- intervals[i] = new Interval[curIntervals.size()];
- for(int j = 0; j < curIntervals.size(); j++) {
- Interval interval = curIntervals.get(j);
- intervals[i][j] = interval;
- interval = curIntervals.get(j);
- int dist = interval.to - interval.start;
- if(dist >= t) {
- if(res == null || res.start > interval.start) {
- res = interval;
- }
- }
- }
- continue;
- }
- Interval[] prev = intervals[i-1];
- int pointer = 0;
- for(int j = 0; j < x[i].length / 2; j++) {
- int from = x[i][j*2];
- int to = x[i][j*2+1];
- if(from == to) continue;
- List<Interval> now = new ArrayList<Interval>();
- now.add(new Interval(i, from, from, from, null));
- while (pointer < prev.length) {
- Interval prevInterval = prev[pointer];
- if(prevInterval.to < from) {
- pointer++;
- continue;
- }
- if(prevInterval.from + 1 >= to) {
- break;
- }
- int nf = prevInterval.from + 1;
- int nt = prevInterval.to + 1;
- if(nf < from) {
- nf = from;
- }
- if(nt > to) {
- nt = to;
- }
- now.add(new Interval(i, nf, nt, prevInterval.start, prevInterval));
- if(prevInterval.to <= to) pointer++;
- else break;
- }
- Interval prevInterval = now.get(0);
- for(int k = 1; k < now.size(); k++) {
- Interval curInterval = now.get(k);
- if(prevInterval.start <= curInterval.start) {
- prevInterval.to = curInterval.to;
- } else {
- prevInterval.to = curInterval.from;
- if(prevInterval.from != prevInterval.to) curIntervals.add(prevInterval);
- prevInterval = curInterval;
- }
- }
- prevInterval.to = to;
- curIntervals.add(prevInterval);
- }
- intervals[i] = new Interval[curIntervals.size()];
- for(int j = 0; j < curIntervals.size(); j++) {
- Interval interval = curIntervals.get(j);
- intervals[i][j] = interval;
- interval = curIntervals.get(j);
- int dist = interval.to - interval.start;
- if(dist >= t) {
- if(res == null || res.start > interval.start) {
- res = interval;
- }
- }
- }
- }
- out.println(res.start);
- List<Integer> changes = new ArrayList<Integer>();
- while(true) {
- if(res.prev == null) {
- break;
- }
- Interval prev = res.prev;
- int time = res.from;
- if(prev.from > time) {
- time = prev.from+1;
- }
- changes.add(time);
- res = prev;
- }
- out.println((res.hall+1) + " " + changes.size());
- Collections.reverse(changes);
- for(int i: changes) {
- out.print(i + " ");
- }
- }
- void init() throws FileNotFoundException {
- if (ONLINE_JUDGE) {
- in = new BufferedReader(new InputStreamReader(System.in));
- out = new PrintWriter(System.out);
- } else {
- in = new BufferedReader(new FileReader("input.txt"));
- out = new PrintWriter("output.txt");
- }
- }
- String readString() throws IOException {
- while (!tok.hasMoreTokens()) {
- tok = new StringTokenizer(in.readLine());
- }
- return tok.nextToken();
- }
- int readInt() throws IOException {
- return Integer.parseInt(readString());
- }
- long readLong() throws IOException {
- return Long.parseLong(readString());
- }
- double readDouble() throws IOException {
- return Double.parseDouble(readString());
- }
- int[] readArr(int n) throws IOException {
- int[] res = new int[n];
- for (int i = 0; i < n; i++) {
- res[i] = readInt();
- }
- return res;
- }
- long[] readArrL(int n) throws IOException {
- long[] res = new long[n];
- for (int i = 0; i < n; i++) {
- res[i] = readLong();
- }
- return res;
- }
- public static void main(String[] args) {
- new C_AA_NIGHT().run();
- }
- public void run() {
- try {
- long t1 = System.currentTimeMillis();
- init();
- solve();
- out.close();
- long t2 = System.currentTimeMillis();
- System.err.println("Time = " + (t2 - t1));
- } catch (Exception e) {
- e.printStackTrace(System.err);
- System.exit(-1);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement