1713: 滑动窗口(单调队列)

文件提交:无需freopen 内存限制:128 MB 时间限制:1.000 S
评测方式:普通裁判 命题人:
提交:1 解决:1

题目描述

      给你一个长度为N的数组,一个长为K的滑动的窗体从最左移至最右端,你只能见到窗口的K个数,每次窗体向右移动一位,如下表:

Window position

Min value

Max value

[ 1 3 -1 ] -3 5 3 6 7

-1

3

1 [ 3 -1 -3 ] 5 3 6 7

-3

3

1 3 [ -1 -3 5 ] 3 6 7

-3

5

1 3 -1 [ -3 5 3 ] 6 7

-3

5

1 3 -1 -3 [ 5 3 6 ] 7

3

6

1 3 -1 -3 5 [ 3 6 7 ]

3

7

你的任务是找出窗口在各位置时的max valuemin value. 

数据范围: 
20%: n<=500; 50%: n<=100000; 
100%: n<=1000000;

输入

第1行nk第2行为长度为n的数组

输出

2行,第1行每个位置的min value第2行每个位置的max value

样例输入

8 3 
1 3 -1 -3 5 3 6 7

样例输出

-1 -3 -3 -3 3 3
3 3 5 5 6 7