najimCseJu

Untitled

Oct 6th, 2019
259
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.31 KB | None | 0 0
  1. package com.example.interviewprep.vizrt;
  2.  
  3. import java.io.*;
  4. import java.util.*;
  5.  
  6. public class Coffee_ITR {
  7.  
  8.     public static void main(String[] args) throws IOException {
  9.         try (Reader reader = new Reader();
  10.              PrintWriter out = new PrintWriter(System.out)) {
  11.             long l;
  12.             int a, b, t, r, n;
  13.             l = reader.nextLong();
  14.             a = reader.nextInt();
  15.             b = reader.nextInt();
  16.             t = reader.nextInt();
  17.             r = reader.nextInt();
  18.             n = reader.nextInt();
  19.             if (n == 0) {
  20.                 out.println(0);
  21.                 return;
  22.             }
  23.             long[][] intervals = new long[n + 1][3]; // 12MB
  24.             int next[] = new int[n];// 1 MB
  25.             Arrays.fill(next, -1);
  26.             for (int i = 0; i < n; i++) intervals[i][0] = reader.nextLong();
  27.             for (int i = 0; i < n; i++) {
  28.                 long x = intervals[i][0] + a * t;
  29.                 long y = x + b * r;
  30.                 intervals[i][1] = Math.min(x, l);
  31.                 intervals[i][2] = Math.min(y, l);
  32.             }
  33.             intervals[n][0] = intervals[n][1] = intervals[n][2] = l;
  34.             /*
  35.              * Finding rightmost coffee shop that intersects with current shops interval
  36.              * Two pointer approach, Complexity O(n)
  37.              * */
  38.             int right = 0;
  39.             for (int i = 0; i < n; i++) {
  40.                 right = Math.max(right, i + 1);
  41.                 while (right < n && intervals[right][0] >= intervals[i][0] && intervals[right][0] <= intervals[i][2]) {
  42.                     right++;
  43.                 }
  44.                 next[i] = right - 1;
  45.                 if (next[i] == i) next[i] = -1;
  46.             }
  47.             long dp[] = new long[n + 1]; // 4MB
  48.             dp[n] = 0;
  49.             int nextPos[] = new int[n + 1];
  50.             for (int i = n - 1; i >= 0; i--) {
  51.                 if (next[i] == -1) {
  52.                     dp[i] = dp[i + 1] + intervals[i][2] - intervals[i][1];
  53.                     nextPos[i] = i + 1;
  54.                 } else {
  55.                     long op1 = dp[next[i]] + Math.max(0, Math.min(intervals[next[i]][0], intervals[i][2]) - intervals[i][1]);
  56.                     long op2 = dp[next[i] + 1] + intervals[i][2] - intervals[i][1];
  57.                     if (op1 > op2) {
  58.                         dp[i] = op1;
  59.                         nextPos[i] = next[i];
  60.                     } else {
  61.                         dp[i] = op2;
  62.                         nextPos[i] = next[i] + 1;
  63.                     }
  64.                 }
  65.             }
  66.  
  67.             LinkedList<Integer> ans = new LinkedList<>();
  68.             int p = 0;
  69.             while (p != n) {
  70.                 ans.addLast(p);
  71.                 p = nextPos[p];
  72.             }
  73.             boolean isSpace = false;
  74.             out.println(ans.size());
  75.             for (int an : ans) {
  76.                 if (isSpace) out.print(" ");
  77.                 out.print(an);
  78.                 isSpace = true;
  79.             }
  80.         }
  81.     }
  82.  
  83.  
  84.     public static class Reader implements Closeable {
  85.         public BufferedReader reader;
  86.         public StringTokenizer tokenizer;
  87.  
  88.         public Reader() {
  89.             reader = new BufferedReader(new InputStreamReader(System.in), 32768);
  90.             tokenizer = null;
  91.         }
  92.  
  93.         public Reader(String filePath) throws FileNotFoundException {
  94.             reader = new BufferedReader(new FileReader(filePath), 32768);
  95.             tokenizer = null;
  96.         }
  97.  
  98.         public String next() {
  99.             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  100.                 try {
  101.                     tokenizer = new StringTokenizer(reader.readLine());
  102.                 } catch (IOException e) {
  103.                     throw new RuntimeException(e);
  104.                 }
  105.             }
  106.             return tokenizer.nextToken();
  107.         }
  108.  
  109.         public String nextLine() throws IOException {
  110.             return reader.readLine();
  111.         }
  112.  
  113.         public int nextInt() {
  114.             return Integer.parseInt(next());
  115.         }
  116.  
  117.         public long nextLong() {
  118.             return Long.parseLong(next());
  119.         }
  120.  
  121.         @Override
  122.         public void close() throws IOException {
  123.             this.reader.close();
  124.         }
  125.     }
  126.     /** ***************Helper Methods Ends Here****** */
  127.  
  128. }
Advertisement
Add Comment
Please, Sign In to add comment