test/aoj/DSL_3_D.sparsetable.test.cpp

• View this file on GitHub
• Last update: 2024-09-20 12:04:43+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/3/DSL_3_D

Depends on

• Sparse-Table (src/DataStructure/SparseTable.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/3/DSL_3_D
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 128
#include <iostream>
#include <vector>
#include "src/DataStructure/SparseTable.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, L;
 cin >> N >> L;
 vector<int> a(N);
 for (int i= 0; i < N; i++) cin >> a[i];
 SparseTable st(a, [](int l, int r) { return min(l, r); });
 for (int i= 0; i + L <= N; i++) cout << st.prod(i, i + L) << " \n"[i + L == N];
 return 0;
}

#line 1 "test/aoj/DSL_3_D.sparsetable.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/3/DSL_3_D
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 128
#include <iostream>
#include <vector>
#line 3 "src/DataStructure/SparseTable.hpp"
template <class T, class F> class SparseTable {
 std::vector<std::vector<T>> dat;
 F f;
public:
 SparseTable() {}
 SparseTable(const std::vector<T> &v, const F &f): f(f) {
  int n= v.size(), log= n > 1 ? 31 - __builtin_clz(n - 1) : 0;
  dat.resize(log + 1), dat[0].assign(v.begin(), v.end());
  for (int i= 0, I= 1, j; i < log; ++i, I<<= 1)
   for (dat[i + 1].resize(j= dat[i].size() - I); j--;) dat[i + 1][j]= f(dat[i][j], dat[i][j + I]);
 }
 // [l, r)
 T prod(int l, int r) const {
  if (r == l + 1) return dat[0][l];
  int k= 31 - __builtin_clz(r - l - 1);
  return f(dat[k][l], dat[k][r - (1 << k)]);
 }
};
#line 7 "test/aoj/DSL_3_D.sparsetable.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, L;
 cin >> N >> L;
 vector<int> a(N);
 for (int i= 0; i < N; i++) cin >> a[i];
 SparseTable st(a, [](int l, int r) { return min(l, r); });
 for (int i= 0; i + L <= N; i++) cout << st.prod(i, i + L) << " \n"[i + L == N];
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00_sample_00.in	AC	5 ms	4 MB
g++-13	01_small_00.in	AC	5 ms	4 MB
g++-13	01_small_01.in	AC	4 ms	4 MB
g++-13	01_small_02.in	AC	4 ms	4 MB
g++-13	02_corner_00.in	AC	4 ms	4 MB
g++-13	02_corner_01.in	AC	4 ms	4 MB
g++-13	02_corner_02.in	AC	4 ms	4 MB
g++-13	02_corner_03.in	AC	4 ms	4 MB
g++-13	03_rand_00.in	AC	4 ms	4 MB
g++-13	03_rand_01.in	AC	4 ms	4 MB
g++-13	03_rand_02.in	AC	4 ms	4 MB
g++-13	03_rand_03.in	AC	4 ms	4 MB
g++-13	03_rand_04.in	AC	4 ms	4 MB
g++-13	03_rand_05.in	AC	4 ms	4 MB
g++-13	03_rand_06.in	AC	4 ms	4 MB
g++-13	03_rand_07.in	AC	4 ms	4 MB
g++-13	04_large_00.in	AC	4 ms	4 MB
g++-13	04_large_01.in	AC	5 ms	4 MB
g++-13	04_large_02.in	AC	5 ms	4 MB
g++-13	04_large_03.in	AC	6 ms	4 MB
g++-13	04_large_04.in	AC	5 ms	4 MB
g++-13	04_large_05.in	AC	5 ms	4 MB
g++-13	04_large_06.in	AC	16 ms	10 MB
g++-13	04_large_07.in	AC	41 ms	25 MB
g++-13	05_maximum_00.in	AC	121 ms	81 MB
g++-13	05_maximum_01.in	AC	125 ms	81 MB
g++-13	05_maximum_02.in	AC	130 ms	81 MB
g++-13	05_maximum_03.in	AC	145 ms	81 MB
g++-13	05_maximum_04.in	AC	134 ms	81 MB
g++-13	05_maximum_05.in	AC	133 ms	81 MB
g++-13	05_maximum_06.in	AC	134 ms	81 MB
g++-13	05_maximum_07.in	AC	126 ms	81 MB
g++-13	06_all_00.in	AC	126 ms	81 MB
g++-13	06_all_01.in	AC	121 ms	81 MB
g++-13	06_all_02.in	AC	120 ms	81 MB
g++-13	06_all_03.in	AC	118 ms	81 MB
g++-13	06_sorted_00.in	AC	123 ms	81 MB
g++-13	06_sorted_01.in	AC	123 ms	81 MB
g++-13	07_extreme_00.in	AC	108 ms	81 MB
g++-13	07_extreme_01.in	AC	105 ms	81 MB
g++-13	07_extreme_02.in	AC	109 ms	81 MB
g++-13	07_extreme_03.in	AC	148 ms	81 MB
clang++-18	00_sample_00.in	AC	5 ms	4 MB
clang++-18	01_small_00.in	AC	4 ms	4 MB
clang++-18	01_small_01.in	AC	4 ms	4 MB
clang++-18	01_small_02.in	AC	4 ms	4 MB
clang++-18	02_corner_00.in	AC	4 ms	4 MB
clang++-18	02_corner_01.in	AC	4 ms	4 MB
clang++-18	02_corner_02.in	AC	4 ms	4 MB
clang++-18	02_corner_03.in	AC	4 ms	4 MB
clang++-18	03_rand_00.in	AC	4 ms	4 MB
clang++-18	03_rand_01.in	AC	4 ms	4 MB
clang++-18	03_rand_02.in	AC	4 ms	4 MB
clang++-18	03_rand_03.in	AC	4 ms	4 MB
clang++-18	03_rand_04.in	AC	4 ms	4 MB
clang++-18	03_rand_05.in	AC	4 ms	4 MB
clang++-18	03_rand_06.in	AC	4 ms	4 MB
clang++-18	03_rand_07.in	AC	4 ms	4 MB
clang++-18	04_large_00.in	AC	5 ms	4 MB
clang++-18	04_large_01.in	AC	5 ms	4 MB
clang++-18	04_large_02.in	AC	5 ms	4 MB
clang++-18	04_large_03.in	AC	5 ms	4 MB
clang++-18	04_large_04.in	AC	5 ms	4 MB
clang++-18	04_large_05.in	AC	5 ms	4 MB
clang++-18	04_large_06.in	AC	16 ms	10 MB
clang++-18	04_large_07.in	AC	41 ms	25 MB
clang++-18	05_maximum_00.in	AC	117 ms	81 MB
clang++-18	05_maximum_01.in	AC	123 ms	81 MB
clang++-18	05_maximum_02.in	AC	133 ms	81 MB
clang++-18	05_maximum_03.in	AC	131 ms	81 MB
clang++-18	05_maximum_04.in	AC	131 ms	81 MB
clang++-18	05_maximum_05.in	AC	133 ms	81 MB
clang++-18	05_maximum_06.in	AC	127 ms	81 MB
clang++-18	05_maximum_07.in	AC	123 ms	81 MB
clang++-18	06_all_00.in	AC	130 ms	81 MB
clang++-18	06_all_01.in	AC	118 ms	81 MB
clang++-18	06_all_02.in	AC	125 ms	81 MB
clang++-18	06_all_03.in	AC	121 ms	81 MB
clang++-18	06_sorted_00.in	AC	125 ms	81 MB
clang++-18	06_sorted_01.in	AC	131 ms	81 MB
clang++-18	07_extreme_00.in	AC	102 ms	81 MB
clang++-18	07_extreme_01.in	AC	100 ms	81 MB
clang++-18	07_extreme_02.in	AC	103 ms	81 MB
clang++-18	07_extreme_03.in	AC	131 ms	81 MB

Back to top page