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	18 ms	16 MB
g++	01_small_00.in	AC	12 ms	16 MB
g++	01_small_01.in	AC	11 ms	16 MB
g++	01_small_02.in	AC	11 ms	16 MB
g++	02_corner_00.in	AC	12 ms	16 MB
g++	02_corner_01.in	AC	12 ms	16 MB
g++	02_corner_02.in	AC	11 ms	16 MB
g++	02_corner_03.in	AC	11 ms	16 MB
g++	03_rand_00.in	AC	12 ms	16 MB
g++	03_rand_01.in	AC	11 ms	16 MB
g++	03_rand_02.in	AC	11 ms	16 MB
g++	03_rand_03.in	AC	11 ms	16 MB
g++	03_rand_04.in	AC	11 ms	16 MB
g++	03_rand_05.in	AC	11 ms	16 MB
g++	03_rand_06.in	AC	12 ms	16 MB
g++	03_rand_07.in	AC	12 ms	16 MB
g++	04_large_00.in	AC	12 ms	16 MB
g++	04_large_01.in	AC	12 ms	17 MB
g++	04_large_02.in	AC	13 ms	17 MB
g++	04_large_03.in	AC	14 ms	17 MB
g++	04_large_04.in	AC	14 ms	17 MB
g++	04_large_05.in	AC	14 ms	17 MB
g++	04_large_06.in	AC	61 ms	25 MB
g++	04_large_07.in	AC	174 ms	46 MB
g++	05_maximum_00.in	AC	594 ms	118 MB
g++	05_maximum_01.in	AC	663 ms	118 MB
g++	05_maximum_02.in	AC	671 ms	118 MB
g++	05_maximum_03.in	AC	690 ms	118 MB
g++	05_maximum_04.in	AC	732 ms	118 MB
g++	05_maximum_05.in	AC	716 ms	118 MB
g++	05_maximum_06.in	AC	709 ms	118 MB
g++	05_maximum_07.in	AC	700 ms	118 MB
g++	06_all_00.in	AC	636 ms	118 MB
g++	06_all_01.in	AC	642 ms	118 MB
g++	06_all_02.in	AC	642 ms	118 MB
g++	06_all_03.in	AC	647 ms	118 MB
g++	06_sorted_00.in	AC	647 ms	118 MB
g++	06_sorted_01.in	AC	637 ms	118 MB
g++	07_extreme_00.in	AC	530 ms	118 MB
g++	07_extreme_01.in	AC	514 ms	118 MB
g++	07_extreme_02.in	AC	534 ms	118 MB
g++	07_extreme_03.in	AC	712 ms	118 MB
clang++	00_sample_00.in	AC	11 ms	14 MB
clang++	01_small_00.in	AC	11 ms	14 MB
clang++	01_small_01.in	AC	11 ms	14 MB
clang++	01_small_02.in	AC	11 ms	12 MB
clang++	02_corner_00.in	AC	11 ms	16 MB
clang++	02_corner_01.in	AC	11 ms	14 MB
clang++	02_corner_02.in	AC	11 ms	16 MB
clang++	02_corner_03.in	AC	11 ms	14 MB
clang++	03_rand_00.in	AC	11 ms	14 MB
clang++	03_rand_01.in	AC	11 ms	16 MB
clang++	03_rand_02.in	AC	11 ms	14 MB
clang++	03_rand_03.in	AC	11 ms	16 MB
clang++	03_rand_04.in	AC	11 ms	14 MB
clang++	03_rand_05.in	AC	11 ms	14 MB
clang++	03_rand_06.in	AC	11 ms	14 MB
clang++	03_rand_07.in	AC	11 ms	14 MB
clang++	04_large_00.in	AC	11 ms	14 MB
clang++	04_large_01.in	AC	11 ms	14 MB
clang++	04_large_02.in	AC	13 ms	14 MB
clang++	04_large_03.in	AC	13 ms	16 MB
clang++	04_large_04.in	AC	13 ms	12 MB
clang++	04_large_05.in	AC	14 ms	14 MB
clang++	04_large_06.in	AC	50 ms	21 MB
clang++	04_large_07.in	AC	141 ms	45 MB
clang++	05_maximum_00.in	AC	467 ms	117 MB
clang++	05_maximum_01.in	AC	525 ms	113 MB
clang++	05_maximum_02.in	AC	562 ms	117 MB
clang++	05_maximum_03.in	AC	566 ms	117 MB
clang++	05_maximum_04.in	AC	606 ms	115 MB
clang++	05_maximum_05.in	AC	585 ms	113 MB
clang++	05_maximum_06.in	AC	598 ms	115 MB
clang++	05_maximum_07.in	AC	589 ms	113 MB
clang++	06_all_00.in	AC	522 ms	113 MB
clang++	06_all_01.in	AC	519 ms	113 MB
clang++	06_all_02.in	AC	505 ms	117 MB
clang++	06_all_03.in	AC	511 ms	115 MB
clang++	06_sorted_00.in	AC	518 ms	117 MB
clang++	06_sorted_01.in	AC	513 ms	115 MB
clang++	07_extreme_00.in	AC	400 ms	113 MB
clang++	07_extreme_01.in	AC	395 ms	115 MB
clang++	07_extreme_02.in	AC	409 ms	113 MB
clang++	07_extreme_03.in	AC	593 ms	115 MB

Back to top page