PKU 2823 Sliding Window

http://poj.org/problem?id=2823
n個の数字の列が与えられる。
この数列から連続するk個の要素の中の最小値と最大値を順番に出力していくという問題。

segmenttreeを書きたくないばかりに、楽をしようとしてTLEやWAをもらい続けていた問題。

treemapへの出し入れよりも、入出力に圧倒的に時間がかかっていました。
最終的にはjavaの高速な出力を使うことで結構ギリギリな気がしますがTLEを回避しました。
あと、複数テストケースの問題のようで、微妙にそれにもはまりました。

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

/*
  http://poj.org/problem?id=2823
*/

public class Main{
    static int[] in=new int[1000000];
    static int[] uans=new int[1000000],lans=new int[1000000];
    public static void main(String[] args){
        Scanner cin=new Scanner(System.in);
        while(cin.hasNextInt()){
            TreeMap<Integer,Integer> app=new TreeMap<Integer,Integer>();            
            int n=cin.nextInt();
            int k=cin.nextInt();

            for(int i=0;i<n;++i)in[i]=cin.nextInt();

            for(int i=0;i<k-1;++i){
                if(app.containsKey(in[i]))app.put(in[i],app.get(in[i])+1);
                else app.put(in[i],1);
            }
            
            for(int i=0;i<n-k+1;++i){
                if(app.containsKey(in[k+i-1]))app.put(in[k+i-1],app.get(in[k+i-1])+1);
                else app.put(in[k+i-1],1);
                lans[i]=app.firstKey();
                uans[i]=app.lastKey();
                if(app.get(in[i])<=1)app.remove(in[i]);
                else app.put(in[i],app.get(in[i])-1);
            }

            PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
            for(int i=0;i<n-k+1;++i){
                out.print(lans[i]);
                out.print(' ');
            }
            out.print('\n');

            for(int i=0;i<n-k+1;++i){
                out.print(uans[i]);
                out.print(' ');
            }
            out.print('\n');
            out.flush();
            out.close();
        }
    }
}