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());
            }
        }
    }
}

Your solution's complexity is O(NM), because heap.remove(Object) requires linear time, not O(logN) time.

Just submit a brute-force. The easiest improvement is SQRT decomposition, but it's not needed in this case.