test/static-range-query/SlideMost.test.cpp

View this file on GitHub
Last update: 2023-06-13 08:02:50+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D

Depends on

SlideMost - スライド最小値/最大値 (lib/13-static-range-query/SlideMost.cpp)

Code

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

#include <vector>
#include <iostream>
#include <deque>
using namespace std;
#include "../../lib/13-static-range-query/SlideMost.cpp"

int main(void){
    cin.tie(0);ios::sync_with_stdio(false);
    int N,L; cin >> N >> L;
    vector<int> A(N);
    for(int i=0;i<N;++i) cin >> A[i];
    SlideMost<ValueMin<int>> sld;
    auto B = sld.window(A,L);
    for(int i=L-1;i<N;++i) cout << B[i] << " \n"[i==N-1];
    return 0;
}

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

#include <vector>
#include <iostream>
#include <deque>
using namespace std;
#line 1 "lib/13-static-range-query/SlideMost.cpp"
/*
 * @title SlideMost - スライド最小値/最大値
 * @docs md/static-range-query/SlideMost.md
 */
template<class Operator> class SlideMost {
    using TypeValue = typename Operator::TypeValue;
public:
    SlideMost(void){
    }
    vector<TypeValue> window(vector<TypeValue>& vec, const int& width){
        vector<TypeValue> res(vec.size());
        deque<TypeValue> deq;
        for(int i = 0; i < vec.size(); ++i) {
            while(deq.size() && Operator::func_compare(vec[deq.back()],vec[i]) ) deq.pop_back();
            deq.push_back(i);
            res[i] = vec[deq.front()];
            if(i+1>=width && deq.front()==i+1-width) deq.pop_front();
        }
        return res;
    }
};
//最小値クエリ
template<class T> struct ValueMin {
    using TypeValue = T;
    inline static constexpr bool func_compare(TypeValue l,TypeValue r){return l>=r;}
};
//最大値クエリ
template<class T> struct ValueMax {
    using TypeValue = T;
    inline static constexpr bool func_compare(TypeValue l,TypeValue r){return l<=r;}
};
#line 8 "test/static-range-query/SlideMost.test.cpp"

int main(void){
    cin.tie(0);ios::sync_with_stdio(false);
    int N,L; cin >> N >> L;
    vector<int> A(N);
    for(int i=0;i<N;++i) cin >> A[i];
    SlideMost<ValueMin<int>> sld;
    auto B = sld.window(A,L);
    for(int i=L-1;i<N;++i) cout << B[i] << " \n"[i==N-1];
    return 0;
}