test/data-structure/line-container/yosupo-Line-Add-Get-Min.test.cpp

• View this file on GitHub
• Last update: 2023-07-11 10:41:16+08:00
• Problem: https://judge.yosupo.jp/problem/line_add_get_min

Depends on

• library/data-structure/line-container.hpp
• Integer division ($\lfloor \frac{a}{b} \rfloor \lceil \frac{a}{b} \rceil$) (library/math/integer-div.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/line_add_get_min"

#include <iostream>

#include <cassert>

#include "../../../library/data-structure/line-container.hpp"

using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	max_line_container<long long> mx;
	min_line_container<long long> mn;
	for(int i = 0; i < n; i++) {
		long long a, b;
		cin >> a >> b;
		mx.add_line(-a, -b);
		mn.add_line(a, b);
	}
	while(q--) {
		int type;
		cin >> type;
		if(type == 0) {
			long long a, b;
			cin >> a >> b;
			mx.add_line(-a, -b);
			mn.add_line(a, b);
		} else {
			long long x;
			cin >> x;
			long long a = -mx.get(x);
			long long b = mn.get(x);
			assert(a == b);
			cout << a << "\n";
		}
	}
	return 0;
}

#line 1 "test/data-structure/line-container/yosupo-Line-Add-Get-Min.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/line_add_get_min"

#include <iostream>

#include <cassert>

#line 2 "library/data-structure/line-container.hpp"
#include <limits>
#line 4 "library/data-structure/line-container.hpp"
#include <set>
#include <functional>
#line 2 "library/math/integer-div.hpp"

namespace felix {

template<class T>
T floor_div(T a, T b) {
	return a / b - ((a ^ b) < 0 && a % b != 0);
}

template<class T>
T ceil_div(T a, T b) {
	return a / b + ((a ^ b) > 0 && a % b != 0);
}

} // namespace felix

#line 7 "library/data-structure/line-container.hpp"

namespace felix {

namespace internal_line_container {

template<class T>
struct line_t {
	mutable T k, m, p;

	bool operator<(const line_t& o) const { return k < o.k; }
	bool operator<(T x) const { return p < x; }
};

template<class T, bool MAX>
struct line_container : std::multiset<line_t<T>, std::less<>> {
	using base = std::multiset<line_t<T>, std::less<>>;
	using typename base::iterator;
	using base::begin, base::end, base::insert, base::erase, base::empty, base::lower_bound;

	static constexpr T INF = std::numeric_limits<T>::max();

	bool isect(iterator x, iterator y) {
		if(y == end()) {
			x->p = INF;
			return 0;
		}
		if(x->k == y->k) {
			x->p = (x->m > y->m ? INF : -INF);
		} else {
			x->p = floor_div(y->m - x->m, x->k - y->k);
		}
		return x->p >= y->p;
	}

	void add_line(T k, T m) {
		if constexpr(!MAX) {
			k = -k;
			m = -m;
		}
		auto z = insert({k, m, 0}), y = z++, x = y;
		while(isect(y, z)) {
			z = erase(z);
		}
		if(x != begin() && isect(--x, y)) {
			isect(x, y = erase(y));
		}
		while((y = x) != begin() && (--x)->p >= y->p) {
			isect(x, erase(y));
		}
	}

	T get(T x) {
		assert(!empty());
		auto l = *lower_bound(x);
		T ans = l.k * x + l.m;
		if constexpr(!MAX) {
			ans = -ans;
		}
		return ans;
	}
};

} // internal_line_container

template<class T> using min_line_container = internal_line_container::line_container<T, false>;
template<class T> using max_line_container = internal_line_container::line_container<T, true>;

} // namespace felix
#line 6 "test/data-structure/line-container/yosupo-Line-Add-Get-Min.test.cpp"
using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	max_line_container<long long> mx;
	min_line_container<long long> mn;
	for(int i = 0; i < n; i++) {
		long long a, b;
		cin >> a >> b;
		mx.add_line(-a, -b);
		mn.add_line(a, b);
	}
	while(q--) {
		int type;
		cin >> type;
		if(type == 0) {
			long long a, b;
			cin >> a >> b;
			mx.add_line(-a, -b);
			mn.add_line(a, b);
		} else {
			long long x;
			cin >> x;
			long long a = -mx.get(x);
			long long b = mn.get(x);
			assert(a == b);
			cout << a << "\n";
		}
	}
	return 0;
}

Back to top page