gistfile1.java

import java.util.*;
import java.io.*;

public class MedianMaintenance {

    public static long sumMedians(List<Integer> xs) {

	Queue<Integer> low = new PriorityQueue<>();
	Queue<Integer> high = new PriorityQueue<>();

	Integer head = xs.get(0);

	long result = head;
	low.add(-head);

	for (int k = 1; k < xs.size(); k++) {
	    Integer i = xs.get(k);

	    if (i < -low.peek())
		low.add(-i);
	    else
		high.add(i);

	    if (low.size() - high.size() > 1)
		high.add(-low.poll());
	    else if (high.size() - low.size() > 1)
		low.add(-high.poll());

	    int j = low.size() + high.size();
	    if ((j & 1) == 0)
		result += -low.peek();
	    else
		result += low.size() > high.size() ? -low.peek() : high.peek();

	}

	return result;
    }

    public static void main (String[] args) throws IOException {
	System.out.println("result : " + sumMedians(readInts()  % 10000));
    }

    public static List<Integer> readInts() throws IOException{
	List<Integer> ret = new ArrayList<>();
	try (BufferedReader bf =
	     new BufferedReader(new FileReader("Median.txt"))) {
		String line;
		while ((line = bf.readLine()) != null)
		    ret.add(Integer.parseInt(line));
	    }
	return ret;
    }

}