Verify/sliding_window.test.cpp

• View this file on GitHub
• Last update: 2020-07-26 22:31:04+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_3_D

Depends on

• DataStructure/sliding_window.hpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_3_D"

#include "../DataStructure/sliding_window.hpp"

#include <iostream>

int main() {
    std::cin.tie();
    std::ios::sync_with_stdio(false);

    int n, l;
    std::cin >> n >> l;

    SlidingWindow<int> sw([](int lhs, int rhs) { return lhs <= rhs; });

    for (int i = 0; i < n; ++i) {
        int a;
        std::cin >> a;
        sw.push(a);

        if (i >= l - 1) {
            std::cout << sw.get() << " \n"[i == n - 1];
            sw.pop();
        }
    }

    return 0;
}

#line 1 "Verify/sliding_window.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_3_D"

#line 2 "DataStructure/sliding_window.hpp"

#include <deque>
#include <functional>

template <class T>
struct SlidingWindow {
    using Cmp = std::function<bool(T, T)>;

    std::deque<std::pair<T, int>> window;
    Cmp cmp;
    int l, r;

    explicit SlidingWindow(Cmp cmp)
        : window(), cmp(cmp), l(0), r(0) {}

    void push(T val) {
        while (!window.empty() && cmp(val, window.back().first)) {
            window.pop_back();
        }
        window.emplace_back(val, r++);
    }

    T get() {
        return window.front().first;
    }

    void pop() {
        if (window.front().second == l++) {
            window.pop_front();
        }
    }
};
#line 4 "Verify/sliding_window.test.cpp"

#include <iostream>

int main() {
    std::cin.tie();
    std::ios::sync_with_stdio(false);

    int n, l;
    std::cin >> n >> l;

    SlidingWindow<int> sw([](int lhs, int rhs) { return lhs <= rhs; });

    for (int i = 0; i < n; ++i) {
        int a;
        std::cin >> a;
        sw.push(a);

        if (i >= l - 1) {
            std::cout << sw.get() << " \n"[i == n - 1];
            sw.pop();
        }
    }

    return 0;
}

Back to top page