test/ALPC-J.test.cpp

• View this file on GitHub
• Last update: 2023-03-10 16:51:37+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://atcoder.jp/contests/practice2/submissions/39569939

Depends on

• segmentTree (一点更新・区間演算セグ木) (src/dataStructure/segmentTree.hpp)
• maxMonoid (最大値モノイド) (src/utility/monoid/maxMonoid.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../src/utility/monoid/maxMonoid.hpp"
#include "../src/dataStructure/segmentTree.hpp"

#include <iostream>
#include <vector>
#include <functional>

int main() {
	// std::cin.tie(nullptr);
	// std::ios::sync_with_stdio(false);
	// int N, Q; std::cin >> N >> Q;
	// std::vector A(N, 0);
	// for (auto& Ai : A) {
	// 	std::cin >> Ai;
	// }
	// zawa::segmentTree<zawa::maxMonoid<int>> seg(A);
	// for (int _ = 0 ; _ < Q ; _++) {
	// 	int T; std::cin >> T;
	// 	if (T == 1) {
	// 		int X, V; std::cin >> X >> V;
	// 		seg.set(X - 1, V);
	// 	}
	// 	if (T == 2) {
	// 		int L, R; std::cin >> L >> R;
	// 		std::cout << seg.prod(L - 1, R) << std::endl;
	// 	}
	// 	if (T == 3) {
	// 		int X, V; std::cin >> X >> V;
	// 		auto f = [&](int p) -> bool {
	// 			return p < V;
	// 		};
	// 		std::cout << seg.maxRight(X - 1, f) + 1 << std::endl;
	// 	}
	// }

	std::cout << "Hello World" << std::endl;	
}

/*
 * AtCoder Library Practice Contest - J Segment Tree
 * https://atcoder.jp/contests/practice2/submissions/39569939
 */

#line 1 "test/ALPC-J.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "src/utility/monoid/maxMonoid.hpp"

#include <algorithm>
#include <limits>

namespace zawa {

template <class T>
struct maxMonoid {
	using valueType = T;
	static constexpr valueType identity = std::numeric_limits<valueType>::min();
	static valueType operation(const valueType& a, const valueType& b) {
		return std::max(a, b);
	}
};

};
#line 2 "src/dataStructure/segmentTree.hpp"

#include <vector>
#include <functional>

namespace zawa {

template <class monoid>
class segmentTree {
private:
	using V = typename monoid::valueType;
	std::size_t N;
	std::vector<V> dat;

public:
	segmentTree() {}
	segmentTree(int _N) : N(_N), dat(2 * _N, monoid::identity) {}
	segmentTree(const std::vector<V>& A) : N(A.size()), dat(2 * N, monoid::identity) {
		for (std::size_t i = 0 ; i < A.size() ; i++) {
			dat[i + N] = A[i];
		}
		for (std::size_t i = N - 1 ; i > 0 ; i--) {
			dat[i] = monoid::operation(dat[i << 1], dat[i << 1 | 1]);		
		}
	}

	void set(std::size_t pos, const V& value) {
		pos += N;
		dat[pos] = value;
		while (pos >>= 1) {
			dat[pos] = monoid::operation(dat[pos << 1], dat[pos << 1 | 1]);
		}
	}

	V update(std::size_t pos, const V& value) {
		pos += N;
		do {
			dat[pos] = monoid::operation(dat[pos], value);
		} while (pos >>= 1);
		return dat[pos];
	}

	V prod(std::size_t l, std::size_t r) const {
		V left = monoid::identity, right = monoid::identity;
		for (l += N, r += N ; l < r ; l >>= 1, r >>= 1) {
			if (l & 1) {
				left = monoid::operation(left, dat[l++]);	
			}
			if (r & 1) {
				right = monoid::operation(dat[--r], right);
			}
		}
		return monoid::operation(left, right);
	}

	template <class functionType>
	int maxRight(int l, const functionType& f) const {
		int L = l + N, w = 1;
		V v = monoid::identity;
		for ( ; l + w <= (int)N ; L >>= 1, w <<= 1) {
			if (L & 1) {
			   	if (f(monoid::operation(v, dat[L]))) {
					v = monoid::operation(v, dat[L++]);
					l += w;
				}
				else {
					break;
				}
			}
		}
		while (L <<= 1, w >>= 1) {
			if (l + w <= (int)N and f(monoid::operation(v, dat[L]))) {
				v = monoid::operation(v, dat[L++]);
				l += w;
			}
		}
		return l;
	}

	template <class functionType>
	int minLeft(int r, const functionType& f) const {	
		int R = r + N, w = 1;
		V v = monoid::identity;
		for ( ; r - w >= 0 ; R >>= 1, w <<= 1) {
			if (R & 1) {
				if (f(monoid::operation(dat[R - 1], v))) {
					v = monoid::operation(dat[--R], v);
					r -= w;
				}
				else {
					break;
				}
			}
		}
		while (R <<= 1, w >>= 1) {
			if (r - w >= 0 and f(monoid::operation(dat[R - 1], v))) {
				v = monoid::operation(dat[--R], v);
				r -= w;
			}
		}
		return r;
	}	
};

} // namespace zawa
#line 5 "test/ALPC-J.test.cpp"

#include <iostream>
#line 9 "test/ALPC-J.test.cpp"

int main() {
	// std::cin.tie(nullptr);
	// std::ios::sync_with_stdio(false);
	// int N, Q; std::cin >> N >> Q;
	// std::vector A(N, 0);
	// for (auto& Ai : A) {
	// 	std::cin >> Ai;
	// }
	// zawa::segmentTree<zawa::maxMonoid<int>> seg(A);
	// for (int _ = 0 ; _ < Q ; _++) {
	// 	int T; std::cin >> T;
	// 	if (T == 1) {
	// 		int X, V; std::cin >> X >> V;
	// 		seg.set(X - 1, V);
	// 	}
	// 	if (T == 2) {
	// 		int L, R; std::cin >> L >> R;
	// 		std::cout << seg.prod(L - 1, R) << std::endl;
	// 	}
	// 	if (T == 3) {
	// 		int X, V; std::cin >> X >> V;
	// 		auto f = [&](int p) -> bool {
	// 			return p < V;
	// 		};
	// 		std::cout << seg.maxRight(X - 1, f) + 1 << std::endl;
	// 	}
	// }

	std::cout << "Hello World" << std::endl;	
}

/*
 * AtCoder Library Practice Contest - J Segment Tree
 * https://atcoder.jp/contests/practice2/submissions/39569939
 */

Back to top page