Ganesh1648

Untitled

Nov 2nd, 2022
1,452
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.83 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3. import java.math.*;
  4.  
  5. public class Main {
  6.  
  7.   static StringBuffer str=new StringBuffer();
  8.   static BufferedReader bf;
  9.   static PrintWriter pw;
  10.   static int n;
  11.   static List<Task> tasks;
  12.  
  13.   static class Task{
  14.     int start, end, time;
  15.     Task(int start, int end, int time){
  16.       this.start=start;
  17.       this.end=end;
  18.       this.time=time;
  19.     }
  20.     public String toString(){
  21.       return this.start+" "+this.end+" "+this.time;
  22.     }
  23.   }
  24.  
  25.   // implementation based on idea: https://codeforces.com/blog/entry/108625?#comment-969002
  26.   static void solve(int te) throws Exception{
  27.     Collections.sort(tasks, (p, q) -> p.start-q.start);
  28.     PriorityQueue<Task> pq=new PriorityQueue<>((p, q) -> {
  29.       return ((p.end-p.start+1)-p.time)-((q.end-q.start+1)-q.time);
  30.     });
  31.     long ans=0;
  32.     int globalStart=1;
  33.     for(int i=0;i<n;i++){
  34.       Task cur=tasks.get(i);
  35.       if(!pq.isEmpty()){
  36.         Task top=pq.remove();
  37.         int start=Math.max(top.start, cur.start);
  38.         int end=Math.min(top.end, cur.end);
  39.         int overLap=Math.min(end-start+1, Math.min(top.time, cur.time));
  40.         // System.out.println(top+" -> "+cur+" -> "+ans);
  41.         top.time-=overLap;
  42.         cur.time-=overLap;
  43.         ans+=overLap;
  44.         globalStart=Math.max(globalStart, end+1);
  45.         if(top.time>0){
  46.           top.start=end+1;
  47.           pq.add(top);
  48.         }
  49.         if(cur.time>0){
  50.           cur.start=end+1;
  51.           pq.add(cur);
  52.         }
  53.       }else{
  54.         if(cur.start<globalStart){
  55.           cur.time-=Math.min(globalStart-cur.start, cur.time);
  56.           if(cur.time>0){
  57.             cur.start=globalStart;
  58.             pq.add(cur);
  59.           }
  60.         }else pq.add(cur);
  61.       }
  62.     }
  63.     while(!pq.isEmpty()) ans+=pq.remove().time;
  64.     str.append(ans).append("\n");
  65.   }
  66.  
  67.   public static void main(String[] args) throws java.lang.Exception {
  68.     boolean lenv=true;  
  69.     int te=1;
  70.     if(lenv){
  71.       bf = new BufferedReader(
  72.                           new FileReader("input.txt"));
  73.       pw=new PrintWriter(new
  74.             BufferedWriter(new FileWriter("output.txt")));
  75.     }else{
  76.       bf = new BufferedReader(new InputStreamReader(System.in));
  77.       pw = new PrintWriter(new OutputStreamWriter(System.out));
  78.     }
  79.  
  80.     // int q1 = Integer.parseInt(bf.readLine().trim());
  81.     // for(te=1;te<=q1;te++) {
  82.       n=Integer.parseInt(bf.readLine().trim());
  83.       tasks=new ArrayList<>();
  84.       for(int i=0;i<n;i++){
  85.         String s[]=bf.readLine().trim().split("\\s+");
  86.         int start, end, time;
  87.         start=Integer.parseInt(s[0]);
  88.         end=Integer.parseInt(s[1]);
  89.         time=Integer.parseInt(s[2]);
  90.         tasks.add(new Task(start, end, time));
  91.       }
  92.       solve(te);
  93.     // }
  94.     pw.print(str);
  95.     pw.flush();
  96.     // System.out.println(str);
  97.   }
  98. }
Advertisement
Add Comment
Please, Sign In to add comment