test/aoj/DSL_3_D.test.cpp

• View this file on GitHub
• Last update: 2021-04-15 20:24:09+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D

Depends on

• スライド最小値 (datastructure/slide-min.hpp)

Code

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

#define call_from_test
#include "../../datastructure/slide-min.hpp"
#undef call_from_test

#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n, l; cin >> n >> l;
  vector<int> la(n);
  for (int &a: la) cin >> a;

  vector<int> ret = slideMin(la, l);
  for (int i = 0; i < ret.size(); ++i) {
    if (i > 0) cout << " ";
    cout << la[ret[i]];
  }
  cout << endl;
}

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

#define call_from_test
#line 1 "datastructure/slide-min.hpp"
/**
 * @title スライド最小値
 */
#include <iostream>
#include <deque>
#include <vector>

template <class T>
std::vector<int> slideMin(const std::vector<T>& v, int k) {
  /* vの連続するk区間の最小値のindexのリストを返す */
  std::vector<int> ret;
  std::deque<int> dq;
  int n = v.size();
  for (int i = 0; i < n; ++i) {
    while (dq.size() && v[dq.back()] >= v[i]) dq.pop_back();
    dq.push_back(i);
    if (i - k + 1 >= 0) {
      ret.push_back(dq.front());
      if (dq.front() <= i-k+1) dq.pop_front();
    }
  }
  return ret;
}

#if 0
#include <cassert>
int main() {
  std::vector<int> v = {1, 3, 5, 4, 2};

  int k = 3;
  std::vector<int> ret = slideMin(v, k);
  assert(ret.size() == 3);
  assert(ret[0] == 0);
  assert(ret[1] == 1);
  assert(ret[2] == 4);
}
#endif
#line 5 "test/aoj/DSL_3_D.test.cpp"
#undef call_from_test

#line 9 "test/aoj/DSL_3_D.test.cpp"
using namespace std;

int main() {
  int n, l; cin >> n >> l;
  vector<int> la(n);
  for (int &a: la) cin >> a;

  vector<int> ret = slideMin(la, l);
  for (int i = 0; i < ret.size(); ++i) {
    if (i > 0) cout << " ";
    cout << la[ret[i]];
  }
  cout << endl;
}

Back to top page