POJ 2823

题目大意

暂无

题目解法

暂无

RTFC

//����POJ������TLE
#include <cstdio>
int n, k, a[1000001], que[1000001][2], head, tail;
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    head = tail = 0;
    for (int i = 0; i < k; i++)
    {
        while (head < tail && que[tail - 1][0] > a[i]) tail--;
        que[tail][0] = a[que[tail][1] = i];
        tail++;
    }
    printf("%d ", que[head][0]);
    for (int i = k; i < n; i++)
    {
        while (head < tail && que[tail - 1][0] > a[i]) tail--;
        que[tail][0] = a[que[tail][1] = i];
        tail++;
        while (head < tail && i - que[head][1] >= k) head++;
        printf("%d ", que[head][0]);
    }
    putchar('\n');
    head = tail = 0;
    for (int i = 0; i < k; i++)
    {
        while (head < tail && que[tail - 1][0] < a[i]) tail--;
        que[tail][0] = a[que[tail][1] = i];
        tail++;
    }
    printf("%d ", que[head][0]);
    for (int i = k; i < n; i++)
    {
        while (head < tail && que[tail - 1][0] < a[i]) tail--;
        que[tail][0] = a[que[tail][1] = i];
        tail++;
        while (head < tail && i - que[head][1] >= k) head++;
        printf("%d ", que[head][0]);
    }
    return 0;
}