test/practice90-037.test.cpp

• View this file on GitHub
• Last update: 2023-03-10 17:06:45+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://atcoder.jp/contests/typical90/submissions/39569356

Depends on

• dualSegmentTree (区間更新一点取得セグ木) (src/dataStructure/dualSegmentTree.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/dataStructure/dualSegmentTree.hpp"
#include "../src/utility/monoid/maxMonoid.hpp"

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

using seg = zawa::dualSegmentTree<zawa::maxMonoid<long long>>;
const long long inf = zawa::maxMonoid<long long>::identity;

int main() {
	// int W, N; std::cin >> W >> N;
	// std::vector dp(W + 1, inf);
	// dp[0] = 0LL;
	// for (int _ = 0 ; _ < N ; _++) {
	// 	int L, R, V; std::cin >> L >> R >> V;
	// 	R++;
	// 	seg S(W + 1);
	// 	for (int i = 0 ; i + L <= W ; i++) {
	// 		if (dp[i] != inf) {
	// 			S.update(i + L, std::min(i + R, W + 1), dp[i] + V);
	// 		}
	// 	}
	// 	for (int i = 0 ; i <= W ; i++) {
	// 		dp[i] = std::max(dp[i], S[i]);
	// 	}
	// }
	// std::cout << (dp[W] == inf ? -1LL : dp[W]) << std::endl;

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

/*
 * 競プロ典型90問 037 Don't Leave the Spice
 * https://atcoder.jp/contests/typical90/submissions/39569356
 */

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

#line 2 "src/dataStructure/dualSegmentTree.hpp"

#include <vector>
#include <cassert>

namespace zawa {

template <class monoid>
class dualSegmentTree {
private:
	using O = typename monoid::valueType;
	int N;
	std::vector<O> dat;

	constexpr int left(int v) const {
		return v << 1;
	}

	constexpr int right(int v) const {
		return v << 1 | 1;
	}

	constexpr int parent(int v) const {
		return v >> 1;
	}

	inline void propagate(int v) {
		if (left(v) < (int)dat.size()) {
			dat[left(v)] = monoid::operation(dat[left(v)], dat[v]);
		}
		if (right(v) < (int)dat.size()) {
			dat[right(v)] = monoid::operation(dat[right(v)], dat[v]);
		}
		dat[v] = monoid::identity;
	}

	void push(int v) {
		int height = 31 - __builtin_clz(v);
		for (int i = height ; i >= 1 ; i--) {
			propagate(v >> i);
		}
	}

public:
	dualSegmentTree() {}
	dualSegmentTree(int _N) : N(_N), dat(_N << 1, monoid::identity) {}
	dualSegmentTree(const std::vector<O>& A) : N((int)A.size()), dat(A.size() << 1, monoid::identity) {
		for (int i = 0 ; i < (int)A.size() ; i++) {
			dat[i + N] = A[i];
		}
	}

	O operator[](int i) {
		assert(0 <= i and i < N);
		i += N;
		push(i);
		return dat[i];
	}

	void set(int i, const O& value) {
		assert(0 <= i and i < N);
		i += N;
		push(i);
		dat[i] = value;
	}

	void update(int i, const O& value) {
		assert(0 <= i and i < N);
		i += N;
		push(i);
		dat[i] = monoid::operation(dat[i], value);
	}

	void update(int l, int r, const O& value) {
		assert(0 <= l and l < N);
		assert(l <= r and r <= N);
		if (l == r) {
			return;
		}
		l += N; r += N;
		push(l); push(r - 1);
		for ( ; l < r ; l = parent(l), r = parent(r)) {
			if (l & 1) {
				dat[l] = monoid::operation(dat[l], value);
				l++;
			}
			if (r & 1) {
				r--;
				dat[r] = monoid::operation(dat[r], value);
			}
		}
	}

	inline std::vector<O> _dat() const {
		return dat;
	}
};

} // namespace 
#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 5 "test/practice90-037.test.cpp"

#line 7 "test/practice90-037.test.cpp"
#include <iostream>
#line 9 "test/practice90-037.test.cpp"

using seg = zawa::dualSegmentTree<zawa::maxMonoid<long long>>;
const long long inf = zawa::maxMonoid<long long>::identity;

int main() {
	// int W, N; std::cin >> W >> N;
	// std::vector dp(W + 1, inf);
	// dp[0] = 0LL;
	// for (int _ = 0 ; _ < N ; _++) {
	// 	int L, R, V; std::cin >> L >> R >> V;
	// 	R++;
	// 	seg S(W + 1);
	// 	for (int i = 0 ; i + L <= W ; i++) {
	// 		if (dp[i] != inf) {
	// 			S.update(i + L, std::min(i + R, W + 1), dp[i] + V);
	// 		}
	// 	}
	// 	for (int i = 0 ; i <= W ; i++) {
	// 		dp[i] = std::max(dp[i], S[i]);
	// 	}
	// }
	// std::cout << (dp[W] == inf ? -1LL : dp[W]) << std::endl;

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

/*
 * 競プロ典型90問 037 Don't Leave the Spice
 * https://atcoder.jp/contests/typical90/submissions/39569356
 */

Back to top page