test/aoj/DSL_3_D.slide_min.test.cpp

• View this file on GitHub
• Last update: 2024-01-08 02:22:28+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D

Depends on

• Sliding Window Minimum (data-structure/slide_min.hpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D"

#include "../../data-structure/slide_min.hpp"

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N, L;
    cin >> N >> L;
    vector<int> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];
    SlideMin<int> sm;
    for (int i = 0; i < L; i++) sm.push(a[i]);
    for (int i = L; i < N; i++) {
        cout << sm.get() << " ";
        sm.pop();
        sm.push(a[i]);
    }
    cout << sm.get() << endl;
}

#line 1 "test/aoj/DSL_3_D.slide_min.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D"

#line 2 "data-structure/slide_min.hpp"
#include <deque>
#include <functional>
#include <utility>

template <typename T, typename Compare = std::less<>>
class SlideMin {
   public:
    void push(T x) {
        while (!dq.empty() && !cmp(dq.back().first, x)) dq.pop_back();
        dq.emplace_back(x, r++);
    }

    void pop() {
        if (dq.front().second == l) dq.pop_front();
        ++l;
    }

    T get() const { return dq.front().first; }

   private:
    int l = 0, r = 0;
    std::deque<std::pair<T, int>> dq;
    Compare cmp;
};
#line 4 "test/aoj/DSL_3_D.slide_min.test.cpp"

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N, L;
    cin >> N >> L;
    vector<int> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];
    SlideMin<int> sm;
    for (int i = 0; i < L; i++) sm.push(a[i]);
    for (int i = L; i < N; i++) {
        cout << sm.get() << " ";
        sm.pop();
        sm.push(a[i]);
    }
    cout << sm.get() << endl;
}

Back to top page