FIMO sequence (AOJ 1070)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1070&lang=jp

問題

略

解法

dequeを6個使う。数列の前半部分、後半部分を保持するのに2個。最大値・最小値×前半・後半で4個。
数列は中央で折って、(n+1)/2と(n+1)/2+1番目の数値をdequeのfrontにする。あとは前半・後半部分の先頭への挿入、後半の末尾への挿入、前半・後半の先頭からの削除を実装すれば良い。
実装量が減るようにてきとうに工夫すること。
というかこの問題0,1,4,5のクエリだけで十分なんじゃあ。