Airplane.java

import java.util.*;

class PLC{
    public TreeMap<Integer, Integer> segmentlist = new TreeMap<Integer, Integer>();
    public int upperBound = 0;
    public int lastSlope = 0;
    public int startValue  = 0;
    public int shift       = 0;
    private static int INF = 100000000;
    private int lb() {
        if(segmentlist.isEmpty()){
            return ub();
        }
        return segmentlist.firstKey()+shift;
    }
    private int ub(){
        return upperBound + shift;
    }
    public void setUpperBound(int x){
        upperBound = x - shift;
    }

    private void Restriction(int a, int b){
        restrictionLeft(a);
        restrictionRight(b);
    }

    public void updateSegment(int x, int Delta){
        int xx = x - shift;
        if(!segmentlist.containsKey(xx)){
            segmentlist.put(xx,0);
        }
        segmentlist.put(xx,Delta+segmentlist.get(xx));
        lastSlope += Delta;
    }
    private void removeSegment(int x){
        int Delta = getSlopeDiff(x);
        segmentlist.remove(x-shift);
        lastSlope -= Delta;
    }
    private void removeLeftMostBreakpoint(){
        if(segmentlist.isEmpty()){
            return;
        }
        int x1 = lb();
        int Delta = getSlopeDiff(x1);
        removeSegment(x1);
        int x2 = lb();
        if(!segmentlist.isEmpty()) {
            updateSegment(x2, Delta);
        }
        startValue += Delta*(x2-x1);
    }
    private void removeRightMostBreakpoint(){
        int x2 = segmentlist.lastKey()+shift;
        removeSegment(x2);
        setUpperBound(x2);
    }
    private int getSlopeDiff(int x){
        return segmentlist.get(x-shift);
    }
    public void Add(PLC g){
        PLC f = this;

        int lbb = Math.max(g.lb(),f.lb());
        int ubb = Math.min(g.ub(),f.ub());
        f.Restriction(lbb,ubb);
        g.Restriction(lbb,ubb);

        for(int x : g.segmentlist.keySet()){
            int y = g.segmentlist.get(x);
            f.updateSegment(x + g.shift, y);
        }
        f.startValue = f.startValue + g.startValue;
    }

    private void restrictionLeft(int a){
        if(segmentlist.isEmpty()){
            return;
        }
        updateSegment(a,0);
        while(lb()<a){
            removeLeftMostBreakpoint();
        }
    }

    private void restrictionRight(int b){
        if(segmentlist.isEmpty()){
            return;
        }
        updateSegment(b,0);
        while(ub()>b){
            removeRightMostBreakpoint();
        }
    }

    public void minTransform(int z){
        while(lastSlope > 0 && !segmentlist.isEmpty()){
            removeRightMostBreakpoint();
        }
        updateSegment(ub(), -lastSlope);
        setUpperBound(INF);
        shift+=z;
    }
    public int min(){
        if(segmentlist.isEmpty()){
            return INF;
        }
        int min = startValue;
        while(!segmentlist.isEmpty()){
            removeLeftMostBreakpoint();
            min = Math.min(min,startValue);
        }
        return min;
    }

    public String toString(){
        return segmentlist.toString() + " " + upperBound + " " + startValue + " " + shift + " " + lastSlope;
    }
}


public class Airplane {
    public static PLC gen_func(int a, int b, int lb, int t, int ub){
        PLC f = new PLC();
        f.shift = 0;
        f.setUpperBound(ub);
        f.updateSegment(lb,-b);
        f.updateSegment(t,a+b);
        f.startValue = (t-lb)*b;
        return f;
    }

    public static PLC airplane_flow(int[] a, int[] b, int[] LB, int[] T, int[] UB, int[] S){
        int n = a.length;
        PLC f = gen_func(a[0],b[0],LB[0],T[0],UB[0]);
        for(int i=1;i<n;i++){
            PLC g = gen_func(a[i],b[i],LB[i],T[i],UB[i]);
            f.minTransform(S[i]);
            if(f.segmentlist.isEmpty()){
                return f;
            }
            f.Add(g);
            if(f.segmentlist.isEmpty()){
                return f;
            }
        }
        return f;
    }
}