test/datastructure/sparse_table/aoj_dsl_3_d.test.cpp

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

Depends on

• Sparse Table (src/datastructure/sparse_table.hpp)

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/3/DSL_3_D

#include "src/datastructure/sparse_table.hpp"

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
	int n, l;
	cin >> n >> l;
	vector<int> a(n);
	for (int &e : a) cin >> e;
	SparseTable st(a, [](int a, int b) { return min(a, b); });
	for (int i = 0; i <= n - l; ++i) {
		if (i) cout << " ";
		cout << st.query(i, i + l);
	}
	cout << endl;

	return 0;
}

#line 1 "test/datastructure/sparse_table/aoj_dsl_3_d.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/3/DSL_3_D

#line 1 "src/datastructure/sparse_table.hpp"



#include <vector>
#include <algorithm>

template<class T, class F>
class SparseTable {
private:
	std::vector<std::vector<T>> table;
	std::vector<int> log_table;
	F f;

public:
	SparseTable(std::vector<T> const &v, F f) : f(f) {
		int n = v.size();
		int h = 1;
		while ((1 << h) <= n) ++h;
		table.assign(h, std::vector<T>(n));
		log_table.assign(n + 1, 0);
		for (int i = 2; i <= n; ++i) log_table[i] = log_table[i >> 1] + 1;

		for (int i = 0; i < n; ++i) table[0][i] = v[i];
		for (int i = 1, k = 1; i < h; ++i, k <<= 1)
			for (int j = 0; j < n; ++j)
				table[i][j] = f(table[i - 1][j], table[i - 1][std::min(j + k, n - 1)]);
	}

	T query(int l, int r) { // [l, r)
		int k = log_table[r - l];
		return f(table[k][l], table[k][r - (1 << k)]);
	}
};


#line 4 "test/datastructure/sparse_table/aoj_dsl_3_d.test.cpp"

#line 6 "test/datastructure/sparse_table/aoj_dsl_3_d.test.cpp"
#include <iostream>
#line 8 "test/datastructure/sparse_table/aoj_dsl_3_d.test.cpp"

using namespace std;

int main() {
	int n, l;
	cin >> n >> l;
	vector<int> a(n);
	for (int &e : a) cin >> e;
	SparseTable st(a, [](int a, int b) { return min(a, b); });
	for (int i = 0; i <= n - l; ++i) {
		if (i) cout << " ";
		cout << st.query(i, i + l);
	}
	cout << endl;

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	106 ms	7 MB
g++	01_small_00.in	AC	12 ms	7 MB
g++	01_small_01.in	AC	12 ms	7 MB
g++	01_small_02.in	AC	12 ms	7 MB
g++	02_corner_00.in	AC	12 ms	7 MB
g++	02_corner_01.in	AC	12 ms	7 MB
g++	02_corner_02.in	AC	11 ms	7 MB
g++	02_corner_03.in	AC	11 ms	7 MB
g++	03_rand_00.in	AC	12 ms	7 MB
g++	03_rand_01.in	AC	11 ms	7 MB
g++	03_rand_02.in	AC	11 ms	7 MB
g++	03_rand_03.in	AC	11 ms	7 MB
g++	03_rand_04.in	AC	11 ms	7 MB
g++	03_rand_05.in	AC	12 ms	7 MB
g++	03_rand_06.in	AC	11 ms	7 MB
g++	03_rand_07.in	AC	12 ms	7 MB
g++	04_large_00.in	AC	12 ms	7 MB
g++	04_large_01.in	AC	13 ms	7 MB
g++	04_large_02.in	AC	13 ms	7 MB
g++	04_large_03.in	AC	14 ms	7 MB
g++	04_large_04.in	AC	14 ms	7 MB
g++	04_large_05.in	AC	15 ms	7 MB
g++	04_large_06.in	AC	59 ms	16 MB
g++	04_large_07.in	AC	167 ms	36 MB
g++	05_maximum_00.in	AC	579 ms	108 MB
g++	05_maximum_01.in	AC	613 ms	108 MB
g++	05_maximum_02.in	AC	669 ms	108 MB
g++	05_maximum_03.in	AC	648 ms	108 MB
g++	05_maximum_04.in	AC	697 ms	108 MB
g++	05_maximum_05.in	AC	679 ms	108 MB
g++	05_maximum_06.in	AC	671 ms	108 MB
g++	05_maximum_07.in	AC	665 ms	108 MB
g++	06_all_00.in	AC	594 ms	108 MB
g++	06_all_01.in	AC	591 ms	108 MB
g++	06_all_02.in	AC	574 ms	108 MB
g++	06_all_03.in	AC	581 ms	108 MB
g++	06_sorted_00.in	AC	587 ms	108 MB
g++	06_sorted_01.in	AC	619 ms	108 MB
g++	07_extreme_00.in	AC	481 ms	108 MB
g++	07_extreme_01.in	AC	471 ms	108 MB
g++	07_extreme_02.in	AC	482 ms	108 MB
g++	07_extreme_03.in	AC	663 ms	108 MB
clang++	00_sample_00.in	AC	12 ms	13 MB
clang++	01_small_00.in	AC	11 ms	9 MB
clang++	01_small_01.in	AC	11 ms	13 MB
clang++	01_small_02.in	AC	11 ms	15 MB
clang++	02_corner_00.in	AC	10 ms	11 MB
clang++	02_corner_01.in	AC	10 ms	9 MB
clang++	02_corner_02.in	AC	11 ms	15 MB
clang++	02_corner_03.in	AC	10 ms	9 MB
clang++	03_rand_00.in	AC	11 ms	9 MB
clang++	03_rand_01.in	AC	10 ms	11 MB
clang++	03_rand_02.in	AC	10 ms	7 MB
clang++	03_rand_03.in	AC	10 ms	11 MB
clang++	03_rand_04.in	AC	11 ms	11 MB
clang++	03_rand_05.in	AC	11 ms	11 MB
clang++	03_rand_06.in	AC	10 ms	9 MB
clang++	03_rand_07.in	AC	10 ms	7 MB
clang++	04_large_00.in	AC	11 ms	11 MB
clang++	04_large_01.in	AC	12 ms	13 MB
clang++	04_large_02.in	AC	12 ms	8 MB
clang++	04_large_03.in	AC	13 ms	16 MB
clang++	04_large_04.in	AC	14 ms	14 MB
clang++	04_large_05.in	AC	14 ms	12 MB
clang++	04_large_06.in	AC	59 ms	18 MB
clang++	04_large_07.in	AC	174 ms	43 MB
clang++	05_maximum_00.in	AC	588 ms	111 MB
clang++	05_maximum_01.in	AC	658 ms	113 MB
clang++	05_maximum_02.in	AC	668 ms	113 MB
clang++	05_maximum_03.in	AC	681 ms	109 MB
clang++	05_maximum_04.in	AC	707 ms	111 MB
clang++	05_maximum_05.in	AC	697 ms	111 MB
clang++	05_maximum_06.in	AC	704 ms	115 MB
clang++	05_maximum_07.in	AC	694 ms	113 MB
clang++	06_all_00.in	AC	630 ms	113 MB
clang++	06_all_01.in	AC	628 ms	113 MB
clang++	06_all_02.in	AC	628 ms	113 MB
clang++	06_all_03.in	AC	616 ms	111 MB
clang++	06_sorted_00.in	AC	627 ms	113 MB
clang++	06_sorted_01.in	AC	615 ms	113 MB
clang++	07_extreme_00.in	AC	526 ms	111 MB
clang++	07_extreme_01.in	AC	515 ms	115 MB
clang++	07_extreme_02.in	AC	526 ms	115 MB
clang++	07_extreme_03.in	AC	703 ms	111 MB

Back to top page