test/aoj/DSL_3_D.disjointsparsetable.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

• Disjoint-Sparse-Table (src/DataStructure/DisjointSparseTable.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/DisjointSparseTable.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];
 DisjointSparseTable<int> dst(a, [](int a, int b) { return min(a, b); });
 for (int i= 0; i + L <= N; i++) cout << (i ? " " : "") << dst.prod(i, i + L);
 cout << '\n';
 return 0;
}

#line 1 "test/aoj/DSL_3_D.disjointsparsetable.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 2 "src/DataStructure/DisjointSparseTable.hpp"
#include <bits/stdc++.h>
/**
 * @title Disjoint-Sparse-Table
 * @category データ構造
 * @brief fは結合則をみたす二項演算
 * @brief 構築 O(n log n)
 * @brief query O(1)
 */

// BEGIN CUT HERE

template <class T> struct DisjointSparseTable {
 std::vector<std::vector<T>> ys;
 using F= std::function<T(T, T)>;
 const F f;
 DisjointSparseTable(std::vector<T> xs, F f_): f(f_) {
  int n= 1;
  while (n <= xs.size()) n*= 2;
  xs.resize(n);
  ys.emplace_back(xs);
  for (int h= 1;; ++h) {
   int range= (2 << h), half= range / 2;
   if (range > n) break;
   ys.emplace_back(xs);
   for (int i= half; i < n; i+= range) {
    for (int j= i - 2; j >= i - half; --j) ys[h][j]= f(ys[h][j], ys[h][j + 1]);
    for (int j= i + 1; j < std::min(n, i + half); ++j) ys[h][j]= f(ys[h][j - 1], ys[h][j]);
   }
  }
 }
 T prod(int i, int j) {  // [i, j)
  if (i == --j) return ys[0][i];
  int h= sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(i ^ j);
  return f(ys[h][i], ys[h][j]);
 }
};
#line 7 "test/aoj/DSL_3_D.disjointsparsetable.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];
 DisjointSparseTable<int> dst(a, [](int a, int b) { return min(a, b); });
 for (int i= 0; i + L <= N; i++) cout << (i ? " " : "") << dst.prod(i, i + L);
 cout << '\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	4 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	5 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	5 ms	4 MB
g++-13	04_large_04.in	AC	5 ms	4 MB
g++-13	04_large_05.in	AC	6 ms	4 MB
g++-13	04_large_06.in	AC	25 ms	13 MB
g++-13	04_large_07.in	AC	84 ms	45 MB
g++-13	05_maximum_00.in	AC	195 ms	94 MB
g++-13	05_maximum_01.in	AC	215 ms	95 MB
g++-13	05_maximum_02.in	AC	209 ms	95 MB
g++-13	05_maximum_03.in	AC	219 ms	94 MB
g++-13	05_maximum_04.in	AC	222 ms	95 MB
g++-13	05_maximum_05.in	AC	209 ms	95 MB
g++-13	05_maximum_06.in	AC	209 ms	94 MB
g++-13	05_maximum_07.in	AC	207 ms	94 MB
g++-13	06_all_00.in	AC	211 ms	94 MB
g++-13	06_all_01.in	AC	206 ms	95 MB
g++-13	06_all_02.in	AC	203 ms	95 MB
g++-13	06_all_03.in	AC	199 ms	95 MB
g++-13	06_sorted_00.in	AC	213 ms	95 MB
g++-13	06_sorted_01.in	AC	212 ms	95 MB
g++-13	07_extreme_00.in	AC	181 ms	95 MB
g++-13	07_extreme_01.in	AC	177 ms	95 MB
g++-13	07_extreme_02.in	AC	184 ms	94 MB
g++-13	07_extreme_03.in	AC	214 ms	95 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	5 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	22 ms	13 MB
clang++-18	04_large_07.in	AC	72 ms	45 MB
clang++-18	05_maximum_00.in	AC	181 ms	94 MB
clang++-18	05_maximum_01.in	AC	176 ms	95 MB
clang++-18	05_maximum_02.in	AC	180 ms	94 MB
clang++-18	05_maximum_03.in	AC	201 ms	94 MB
clang++-18	05_maximum_04.in	AC	190 ms	94 MB
clang++-18	05_maximum_05.in	AC	190 ms	95 MB
clang++-18	05_maximum_06.in	AC	177 ms	95 MB
clang++-18	05_maximum_07.in	AC	177 ms	94 MB
clang++-18	06_all_00.in	AC	176 ms	94 MB
clang++-18	06_all_01.in	AC	173 ms	95 MB
clang++-18	06_all_02.in	AC	211 ms	95 MB
clang++-18	06_all_03.in	AC	165 ms	94 MB
clang++-18	06_sorted_00.in	AC	177 ms	94 MB
clang++-18	06_sorted_01.in	AC	174 ms	94 MB
clang++-18	07_extreme_00.in	AC	154 ms	94 MB
clang++-18	07_extreme_01.in	AC	148 ms	95 MB
clang++-18	07_extreme_02.in	AC	153 ms	95 MB
clang++-18	07_extreme_03.in	AC	182 ms	95 MB

Back to top page