[데이터 구조] [luoguP 1886] 슬라이딩 창

제목.
단조 로 운 대기 열 에 가 까 운 템 플 릿 입 니 다.


#include
#include
#include

    using namespace std;
    #define in = read()
    typedef long long ll;
    const ll size = 1000000 + 1000;

        ll n ,k;
        ll a[size];
        ll h ,t; 
        ll q[size] ,p[size];

inline ll read(){

        ll num = 0, f = 1;    char ch = getchar();

        while (!isdigit(ch)){
                if(ch == '-')   f = -1;
                ch = getchar();
        }

        while (isdigit(ch)){
                num = num*10 + ch - '0';
                ch = getchar();
        }

        return num*f;
}

inline void maxx(){

        h = 1;    t = 0;

        for (int i=1;i<=n;i++){

                while (h <= t && q[t] <= a[i])
                        t --;

                q[++ t] = a[i];   p[t] = i;

                while (p[h] <= i - k)
                        h ++;

                if(i >= k)
                        printf("%d ",q[h]);

        }

        printf("
"
); } inline void minn(){ h =1; t = 0; for (int i=1;i<=n;i++){ while (h <= t && q[t] >= a[i]) t --; q[++ t] = a[i]; p[t] = i; while(p[h] <= i - k) h ++; if(i >= k) printf("%d ",q[h]); } printf("
"
); } int main(){ n in; k in; for (int i=1;i<=n;i++) a[i] in; minn(); maxx(); } //COYG

좋은 웹페이지 즐겨찾기