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