fork download
copy 
  1.  
  2. import java.io.BufferedReader;
  3. import java.io.IOException;
  4. import java.io.InputStreamReader;
  5. import java.io.StreamTokenizer;
  6. import java.util.ArrayList;
  7. import java.util.Collections;
  8. import java.util.Iterator;
  9. import java.util.TreeSet;
  10. import java.lang.Integer;
  11.  
  12. public class waterfall_kp {
  13.  
  14.     static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  15.  
  16.     static int nextInt() {
  17.         try {
  18.             st.nextToken();
  19.             return (int) st.nval;
  20.         } catch (IOException ex) {
  21.             return 0;
  22.         }
  23.     }
  24.  
  25.     static class Segment implements Comparable<Segment> {
  26.  
  27.         int l, r, h;
  28.         int max = 0;
  29.  
  30.         public Segment(int l, int r, int h) {
  31.             this.l = l;
  32.             this.r = r;
  33.             this.h = h;
  34.  
  35.         }
  36.  
  37.         @Override
  38.         public int compareTo(Segment o) {
  39.             int cmp = -Integer.valueOf(h).compareTo(Integer.valueOf(o.h));
  40.             return cmp == 0 ? Integer.valueOf(l).compareTo(Integer.valueOf(o.l)) : cmp;
  41.         }
  42.  
  43.         boolean overlaps(Segment o) {
  44.             return l < o.r && o.l < r;
  45.         }
  46.     }
  47.  
  48.     static class Part implements Comparable<Part> {
  49.  
  50.         int l, r;
  51.         Segment s;
  52.  
  53.         public Part(int l, int r, Segment s) {
  54.             this.l = l;
  55.             this.r = r;
  56.             this.s = s;
  57.         }
  58.  
  59.         public Part(Segment s) {
  60.             this.l = s.l;
  61.             this.r = s.r;
  62.             this.s = s;
  63.         }
  64.  
  65.         @Override
  66.         public int compareTo(Part o) {
  67.             int cmp = Integer.valueOf(l).compareTo(Integer.valueOf(o.l));
  68.             return cmp == 0 ? Integer.valueOf(r).compareTo(Integer.valueOf(o.r)) : cmp;
  69.         }
  70.  
  71.         int overlap(Part o) {
  72.             return Math.min(r,o.r)-Math.max(l,o.l);
  73.         }
  74.  
  75.         private int length() {
  76.             return r-l;
  77.         }
  78.     }
  79.  
  80.     public static void main(String[] args) {
  81.         int n = nextInt();
  82.         ArrayList<Segment> segments = new ArrayList<Segment>();
  83.         Segment top = new Segment(Integer.MIN_VALUE, Integer.MAX_VALUE, nextInt());
  84.         top.max = Integer.MAX_VALUE;
  85.         Segment bottom = new Segment(Integer.MIN_VALUE+1, Integer.MAX_VALUE-1, 0);
  86.         segments.add(top);
  87.         segments.add(bottom);
  88.         for (int i = 0; i < n; i++) {
  89.             int h = nextInt();
  90.             segments.add(new Segment(nextInt(), nextInt(), h));
  91.         }
  92.         Collections.sort(segments);
  93.  
  94.         TreeSet<Part> parts = new TreeSet<Part>();
  95.         parts.add(new Part(top));
  96.         for (int i = 1; i < segments.size(); i++) {
  97.             Segment s = segments.get(i);
  98.             Part p = new Part(s);
  99.             Part first = parts.lower(new Part(s.l, s.l, null));
  100.             if(first.r==p.l) {
  101.                 first=parts.higher(first);
  102.             }
  103.             Part last = parts.lower(new Part(s.r, s.r, null));
  104.             TreeSet<Part> oParts = (TreeSet<Part>) parts.subSet(first, true, last, true);
  105.             Iterator<Part> it = oParts.iterator();
  106.  
  107.             Part l = null;
  108.             Part m = null;
  109.             Part r = null;
  110.  
  111.             while (m == null) {
  112.                 m = r;
  113.                 if(it.hasNext()) {
  114.                     r=it.next();
  115.                     it.remove();
  116.                 } else {
  117.                     r=null;
  118.                 }
  119.             }
  120.             while (m != null) {
  121.                 boolean use = true;
  122.                 if (l != null) {
  123.                     if (l.s.overlaps(m.s)&&l.s.h<m.s.h) {
  124.                         use = false;
  125.                     }
  126.                 }
  127.                 if (r != null) {
  128.                     if (r.s.overlaps(m.s)&&r.s.h<m.s.h) {
  129.                         use = false;
  130.                     }
  131.                 }
  132.                 if(use) {
  133.                     s.max=Math.max(s.max,Math.min(m.s.max, p.overlap(m)));
  134.                 }
  135.                 l=m;
  136.                 m=r;
  137.                 if(it.hasNext()) {
  138.                     r=it.next();
  139.                     it.remove();
  140.                 } else {
  141.                     r=null;
  142.                 }
  143.             }
  144.  
  145.             parts.add(p);
  146.             if(p.l>first.l) {
  147.                 parts.add(new Part(first.l,p.l,first.s));
  148.             }
  149.             if(p.r<last.r){
  150.                 parts.add(new Part(p.r,last.r,last.s));
  151.             }
  152.         }
  153.         System.out.println(bottom.max);
  154.     }
  155. }
  156.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/frmAwe
language:
Java (HotSpot 12)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!