verify/slide_min_AOJ_DSL3D.cpp

• View this file on GitHub
• Last update: 2026-02-27 09:54:45+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_3_D

Depends on

• templates/alias.hpp
• templates/macro.hpp
• utils/slide_minmax.hpp

Code

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

#include <bits/stdc++.h>
using namespace std;
#include "templates/alias.hpp"
#include "templates/macro.hpp"
#include "utils/slide_minmax.hpp"

int main() {
  ll N, L;
  in(N, L);
  vi A(N);
  in(A);

  out(slide_min(A, L));
}

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

#include <bits/stdc++.h>
using namespace std;
#line 7 "templates/alias.hpp"

template <class T> using VC = std::vector<T>;
template <class T>
using rpriority_queue = std::priority_queue<T, VC<T>, std::greater<T>>;
using ll = long long;
using ld = long double;
using pii = std::pair<ll, ll>;
using vi = VC<ll>;
using vvi = VC<vi>;
using vvvi = VC<vvi>;
using vb = VC<bool>;
using vvb = VC<vb>;
using vf = VC<double>;
using vvf = VC<vf>;
using vpii = VC<pii>;
using vvpii = VC<vpii>;
using si = std::set<ll>;
using spii = std::set<pii>;
using mii = std::map<ll, ll>;
const std::string upperlist = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const std::string lowerlist = "abcdefghijklmnopqrstuvwxyz";
#define mp make_pair
#define dms << " " <<

constexpr int MOD998 = 998244353;
#line 4 "templates/macro.hpp"

// 引数の長さで内容が変わるrep 参考: https://trap.jp/post/1224
#define overload4(a, b, c, d, ...) d
#define _rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rep(...) overload4(__VA_ARGS__, REP, _rep)(__VA_ARGS__)
#define _rrep(i, n) for (int i = n - 1; i >= 0; i--)
#define RREP(i, a, b) for (int i = (int)(b - 1); i >= (int)(a); i--)
#define rrep(...) overload4(__VA_ARGS__, RREP, _rrep)(__VA_ARGS__)

#define all(a) (a).begin(), (a).end()

template <typename T> bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T> bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

template <typename T1, typename T2>
std::istream &operator>>(std::istream &is, std::pair<T1, T2> &p) {
  is >> p.first >> p.second;
  return is;
}

template <typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
  for (T &in : v)
    is >> in;
  return is;
}

template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
  for (int i = 0; i < (int)v.size(); i++) {
    os << v[i] << (i + 1 == v.size() ? "" : " ");
  }
  return os;
}

// pythonのprintライクな関数 参考:
// https://nyaannyaan.github.io/library/template/inout.hpp
inline void out() { std::cout << std::endl; }
template <typename T, typename... U, char sep = ' '>
void out(const T &t, const U &...u) {
  std::cout << t;

  if (sizeof...(u))
    std::cout << sep;

  out(u...);
}

// cinの短縮関数 参考: https://nyaannyaan.github.io/library/template/inout.hpp
inline void in() {}
template <typename T, class... U> void in(T &t, U &...u) {
  std::cin >> t;
  in(u...);
}

template <typename T> inline T ceil_div(T a, T b) { return (a + b - 1) / b; }
template <typename T> inline T mod_pow(T a, T n, T mod) {
  T res = 1;
  while (n) {
    if (n % 2 != 0) {
      res *= a;
      res %= mod;
    }

    a *= a;
    a %= mod;

    n >>= 1;
  }

  return res;
}
template <typename T> inline T minus_mod(T a, T b) { return ((a % b) + b) % b; }

template <typename T> void apply_vec(std::vector<T> &v, T (*fn)(T)) {
  for (int i = 0; i < v.size(); i++)
    v[i] = fn(v[i]);
}
#line 5 "utils/slide_minmax.hpp"

template <class T> VC<T> slide_min(const VC<T> &v, int k) {
  assert(k <= v.size());
  std::deque<int> Q;

  rep(i, k - 1) {
    while (!Q.empty() && v[Q.back()] >= v[i])
      Q.pop_back();
    Q.emplace_back(i);
  }

  VC<T> res(v.size() - k + 1);

  rep(i, k - 1, v.size()) {
    while (!Q.empty() && v[Q.back()] >= v[i])
      Q.pop_back();
    Q.emplace_back(i);
    res[i - k + 1] = v[Q.front()];

    while (!Q.empty() && Q.front() <= i - k + 1) {
      Q.pop_front();
    }
  }

  return res;
}

template <class T> VC<T> slide_max(const VC<T> &v, int k) {
  assert(k <= v.size());
  std::deque<int> Q;

  rep(i, k - 1) {
    while (!Q.empty() && v[Q.back()] <= v[i])
      Q.pop_back();
    Q.emplace_back(i);
  }

  VC<T> res(v.size() - k + 1);

  rep(i, k - 1, v.size()) {
    while (!Q.empty() && v[Q.back()] <= v[i])
      Q.pop_back();
    Q.emplace_back(i);
    res[i - k + 1] = v[Q.front()];

    while (!Q.empty() && Q.front() <= i - k + 1)
      Q.pop_front();
  }

  return res;
}
#line 9 "verify/slide_min_AOJ_DSL3D.cpp"

int main() {
  ll N, L;
  in(N, L);
  vi A(N);
  in(A);

  out(slide_min(A, L));
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	6 ms	4 MB
g++	01_small_00.in	AC	6 ms	4 MB
g++	01_small_01.in	AC	5 ms	4 MB
g++	01_small_02.in	AC	5 ms	3 MB
g++	02_corner_00.in	AC	5 ms	4 MB
g++	02_corner_01.in	AC	5 ms	4 MB
g++	02_corner_02.in	AC	5 ms	4 MB
g++	02_corner_03.in	AC	5 ms	4 MB
g++	03_rand_00.in	AC	5 ms	4 MB
g++	03_rand_01.in	AC	5 ms	4 MB
g++	03_rand_02.in	AC	5 ms	4 MB
g++	03_rand_03.in	AC	5 ms	4 MB
g++	03_rand_04.in	AC	5 ms	4 MB
g++	03_rand_05.in	AC	5 ms	4 MB
g++	03_rand_06.in	AC	5 ms	4 MB
g++	03_rand_07.in	AC	5 ms	4 MB
g++	04_large_00.in	AC	5 ms	4 MB
g++	04_large_01.in	AC	6 ms	4 MB
g++	04_large_02.in	AC	6 ms	4 MB
g++	04_large_03.in	AC	7 ms	4 MB
g++	04_large_04.in	AC	7 ms	4 MB
g++	04_large_05.in	AC	8 ms	4 MB
g++	04_large_06.in	AC	24 ms	5 MB
g++	04_large_07.in	AC	65 ms	8 MB
g++	05_maximum_00.in	AC	224 ms	19 MB
g++	05_maximum_01.in	AC	275 ms	19 MB
g++	05_maximum_02.in	AC	310 ms	19 MB
g++	05_maximum_03.in	AC	335 ms	19 MB
g++	05_maximum_04.in	AC	349 ms	19 MB
g++	05_maximum_05.in	AC	350 ms	19 MB
g++	05_maximum_06.in	AC	346 ms	19 MB
g++	05_maximum_07.in	AC	338 ms	18 MB
g++	06_all_00.in	AC	272 ms	19 MB
g++	06_all_01.in	AC	282 ms	19 MB
g++	06_all_02.in	AC	292 ms	19 MB
g++	06_all_03.in	AC	271 ms	19 MB
g++	06_sorted_00.in	AC	279 ms	19 MB
g++	06_sorted_01.in	AC	265 ms	19 MB
g++	07_extreme_00.in	AC	153 ms	19 MB
g++	07_extreme_01.in	AC	149 ms	18 MB
g++	07_extreme_02.in	AC	156 ms	19 MB
g++	07_extreme_03.in	AC	350 ms	19 MB
clang++	00_sample_00.in	AC	6 ms	4 MB
clang++	01_small_00.in	AC	6 ms	4 MB
clang++	01_small_01.in	AC	6 ms	4 MB
clang++	01_small_02.in	AC	6 ms	4 MB
clang++	02_corner_00.in	AC	6 ms	4 MB
clang++	02_corner_01.in	AC	5 ms	4 MB
clang++	02_corner_02.in	AC	5 ms	4 MB
clang++	02_corner_03.in	AC	5 ms	4 MB
clang++	03_rand_00.in	AC	5 ms	4 MB
clang++	03_rand_01.in	AC	5 ms	4 MB
clang++	03_rand_02.in	AC	5 ms	4 MB
clang++	03_rand_03.in	AC	6 ms	4 MB
clang++	03_rand_04.in	AC	6 ms	4 MB
clang++	03_rand_05.in	AC	5 ms	4 MB
clang++	03_rand_06.in	AC	5 ms	4 MB
clang++	03_rand_07.in	AC	5 ms	4 MB
clang++	04_large_00.in	AC	6 ms	4 MB
clang++	04_large_01.in	AC	6 ms	4 MB
clang++	04_large_02.in	AC	6 ms	4 MB
clang++	04_large_03.in	AC	6 ms	4 MB
clang++	04_large_04.in	AC	6 ms	4 MB
clang++	04_large_05.in	AC	7 ms	4 MB
clang++	04_large_06.in	AC	24 ms	5 MB
clang++	04_large_07.in	AC	67 ms	8 MB
clang++	05_maximum_00.in	AC	229 ms	19 MB
clang++	05_maximum_01.in	AC	290 ms	19 MB
clang++	05_maximum_02.in	AC	327 ms	19 MB
clang++	05_maximum_03.in	AC	327 ms	19 MB
clang++	05_maximum_04.in	AC	379 ms	19 MB
clang++	05_maximum_05.in	AC	384 ms	19 MB
clang++	05_maximum_06.in	AC	346 ms	19 MB
clang++	05_maximum_07.in	AC	340 ms	18 MB
clang++	06_all_00.in	AC	291 ms	19 MB
clang++	06_all_01.in	AC	272 ms	19 MB
clang++	06_all_02.in	AC	271 ms	19 MB
clang++	06_all_03.in	AC	275 ms	19 MB
clang++	06_sorted_00.in	AC	270 ms	19 MB
clang++	06_sorted_01.in	AC	266 ms	19 MB
clang++	07_extreme_00.in	AC	152 ms	19 MB
clang++	07_extreme_01.in	AC	154 ms	18 MB
clang++	07_extreme_02.in	AC	159 ms	19 MB
clang++	07_extreme_03.in	AC	366 ms	19 MB

Back to top page