Here is my solution. It uses heap(PriorityQueue) and queue(LinkedList). It TLs on 2nd test case. Is there any solution which is asymptotically better than this? What are points to improve?
public class P1126 {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        in.nextToken();
        int m = (int)in.nval;

        PriorityQueue<Integer> heap = new PriorityQueue<Integer>(m, new Comparator<Integer>() {
            public int compare(Integer i, Integer j) {
                return j.compareTo(i);
            }
        });
        LinkedList<Integer>  queue = new LinkedList<Integer>();
        int cur;
        while (true) {
            in.nextToken();
            cur = (int)in.nval;
            if (cur == -1) break;
            heap.add(cur);
            queue.add(cur);
            if (heap.size() == m) {
                System.out.println(heap.peek());
                heap.remove(queue.pollFirst());
            }
        }
    }
}