verify/yosupo/yosupo-line_add_get_min.test.cpp

• View this file on GitHub
• Last update: 2022-07-21 16:12:33-04:00
• Problem: https://judge.yosupo.jp/problem/line_add_get_min

Depends on

• library/contest/template-minimal.hpp
• Line Container (library/dynamic-programming/line-container.hpp)

Code

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

#include "../../library/contest/template-minimal.hpp"
#include "../../library/dynamic-programming/line-container.hpp"

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, q;
	cin >> n >> q;
	LineContainer<long long> cht;	
	while (n--) {
		int a;
		long long b;
		cin >> a >> b;
		cht.add_line(a, b);
	} 
	while (q--) {
		int t;
		cin >> t;
		if (t == 0) {
			int a;
			long long b;
			cin >> a >> b;
			cht.add_line(a, b);
		} else {
			int p;
			cin >> p;
			cout << cht.query(p) << '\n';
		}
	}
	return 0;
}

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


#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

template <class T> struct Line {
	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> struct LineContainer : std::multiset<Line<T>, std::less<>> {
	// (for doubles, use INF = 1/.0, div(a,b) = a/b)

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

	T div(T a, T b) { // floored division

		return a / b - ((a ^ b) < 0 && a % b); 
	}

	using super = std::multiset<Line<T>, std::less<>>;
	using iterator = typename LineContainer<T>::iterator;
	
	bool isect(iterator x, iterator y) {
		if (y == super::end()) 
			return x->p = INF, 0;
		if (x->k == y->k) 
			x->p = x->m > y->m ? INF : -INF;
		else 
			x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	
	void add_line(T k, T m) {
		k = -k, m = -m;
		auto z = super::insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) 
			z = super::erase(z);
		if (x != super::begin() && isect(--x, y)) 
			isect(x, y = super::erase(y));
		while ((y = x) != super::begin() && (--x)->p >= y->p)
			isect(x, super::erase(y));
	}
	
	T query(T x) {
		assert(!super::empty());
		auto l = *super::lower_bound(x);
		return -(l.k * x + l.m);
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, q;
	cin >> n >> q;
	LineContainer<long long> cht;	
	while (n--) {
		int a;
		long long b;
		cin >> a >> b;
		cht.add_line(a, b);
	} 
	while (q--) {
		int t;
		cin >> t;
		if (t == 0) {
			int a;
			long long b;
			cin >> a >> b;
			cht.add_line(a, b);
		} else {
			int p;
			cin >> p;
			cout << cht.query(p) << '\n';
		}
	}
	return 0;
}

Back to top page