sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#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; }