某島

… : "…アッカリ~ン . .. . " .. .
December 25, 2010

POJ 2823. Sliding Window

Brief description:

。。維護一個寬度為 k 的滑動窗口。。分別統計所有位置的最大值和最小值。。

Analysis:

1. C++ 怎麼都過。 / G++ 怎麼都 TLE 。。
2. 「那些500-600MS的代碼到底是怎麼弄出來的。。」。。
.. .

const int N = 1000009;

int a[N], q[N], cz, op;
int n, k;

template<class T> void gao(T cmp){

    cz = 0, op = -1; REP_1(i, k){
        while (cz <= op && cmp(a[i], a[q[op]])) --op;
        q[++op] = i;
    }

    printf("%d ", a[q[cz]]);

    FOR_1(i, k + 1, n){
        if (q[cz] == i - k) ++cz;
        while (cz <= op && cmp(a[i], a[q[op]])) --op;
        q[++op] = i; printf("%d ", a[q[cz]]);

    }

    puts("");
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n, k); REP_1(i, n) RD(a[i]);
    gao(less<int>()), gao(greater<int>());
}

External link:

http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=16694