verify/aoj_dsl/aoj_dsl_3_d.test.cpp

View this file on GitHub
Last update: 2023-02-06 19:40:21+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D

Depends on

Sliding Window Minimum (スライド最小値) (dp/sliding_window_minimum.hpp)

Code

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

#include <bits/stdc++.h>

#include "dp/sliding_window_minimum.hpp"

int main() {
    int N, L;
    std::cin >> N >> L;
    std::vector<int> a(N);
    for (int i = 0; i < N; i++) std::cin >> a[i];
    auto b = sliding_window_minimum(a, L);
    for (int i = 0; i < N - L + 1; i++) std::cout << b[i] << " \n"[i == N - L];
    return 0;
}

#line 1 "verify/aoj_dsl/aoj_dsl_3_d.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D"

#include <bits/stdc++.h>

#line 2 "dp/sliding_window_minimum.hpp"

template <class T> std::vector<T> sliding_window_minimum(const std::vector<T> &a, const int k) {
    int n = (int)a.size();
    std::vector<T> res(n - k + 1);
    std::deque<T> deq;
    for (int i = 0; i < n; i++) {
        while (!deq.empty() and a[deq.back()] >= a[i]) deq.pop_back();
        deq.push_back(i);
        if (i - k + 1 >= 0) {
            res[i - k + 1] = a[deq.front()];
            if (deq.front() == i - k + 1) deq.pop_front();
        }
    }
    return res;
}
#line 6 "verify/aoj_dsl/aoj_dsl_3_d.test.cpp"

int main() {
    int N, L;
    std::cin >> N >> L;
    std::vector<int> a(N);
    for (int i = 0; i < N; i++) std::cin >> a[i];
    auto b = sliding_window_minimum(a, L);
    for (int i = 0; i < N - L + 1; i++) std::cout << b[i] << " \n"[i == N - L];
    return 0;
}