This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/Library
#define PROBLEM "https://judge.yosupo.jp/problem/segment_add_get_min" #include <iostream> #include <utility> #include <vector> #include "../../data_structure/li_chao_tree.hpp" #include "../../template/int_alias.hpp" using ebi::i64; int main() { int n, q; std::cin >> n >> q; std::vector<std::pair<i64, i64>> lr(n); std::vector<std::pair<i64, i64>> y(n); std::vector<i64> x; for (int i = 0; i < n; i++) { std::cin >> lr[i].first >> lr[i].second; std::cin >> y[i].first >> y[i].second; } std::vector<std::vector<i64>> query(q); for (int i = 0; i < q; i++) { i64 t; std::cin >> t; query[i].emplace_back(t); if (t == 0) { i64 l, r, a, b; std::cin >> l >> r >> a >> b; query[i].emplace_back(l); query[i].emplace_back(r); query[i].emplace_back(a); query[i].emplace_back(b); } else { i64 p; std::cin >> p; query[i].emplace_back(p); x.emplace_back(p); } } if (x.size() == 0) return 0; std::sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end()); x.emplace_back(1e9 + 10); ebi::li_chao_tree<i64> seg(x); for (int i = 0; i < n; i++) { auto [l, r] = lr[i]; auto [a, b] = y[i]; seg.add_segment(a, b, l, r); } for (int i = 0; i < q; i++) { if (query[i][0] == 0) { i64 l = query[i][1]; i64 r = query[i][2]; i64 a = query[i][3]; i64 b = query[i][4]; seg.add_segment(a, b, l, r); } else { i64 ret = seg.min(query[i][1]); if (ret == std::numeric_limits<i64>::max()) { std::cout << "INFINITY" << std::endl; } else { std::cout << ret << std::endl; } } } }
#line 1 "test/data_structure/Segment_Add_Get_Min.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/segment_add_get_min" #include <iostream> #include <utility> #include <vector> #line 2 "data_structure/li_chao_tree.hpp" #include <algorithm> #include <cassert> #include <limits> #line 8 "data_structure/li_chao_tree.hpp" namespace ebi { template <class T> struct li_chao_tree { private: T f(std::pair<T, T> y, T x) const { return y.first * x + y.second; } void add(std::pair<T, T> y, int l, int r, int index) { while (l < r) { bool left = f(y, xs[l]) < f(data[index], xs[l]); bool mid = f(y, xs[(l + r) / 2]) < f(data[index], xs[(l + r) / 2]); bool right = f(y, xs[r - 1]) < f(data[index], xs[r - 1]); if (left && right) { data[index] = y; return; } if (!(left || right)) { return; } if (mid) { std::swap(y, data[index]); left = !left; right = !right; } if (left) { r = (l + r) / 2; index *= 2; } else { l = (l + r) / 2; index = 2 * index + 1; } } } int get_index(T x) const { auto itr = std::lower_bound(xs.begin(), xs.end(), x); return itr - xs.begin(); } public: li_chao_tree(std::vector<T> &_x) : xs(_x), sz(1) { std::sort(xs.begin(), xs.end()); xs.erase(std::unique(xs.begin(), xs.end()), xs.end()); while (sz < int(xs.size())) sz <<= 1; while (int(xs.size()) < sz) xs.emplace_back(xs.back() + 1); data.assign(2 * sz, {0, std::numeric_limits<T>::max()}); } void add_line(T a, T b) { add({a, b}, 0, sz, 1); } void add_segment(T a, T b, T lx, T rx) { int l = get_index(lx); int r = get_index(rx); assert(0 <= l && l <= r && r <= sz); int il = l + sz; int ir = r + sz; int rank = 0; while (il < ir) { if (il & 1) { add({a, b}, l, l + (1 << rank), il++); l += (1 << rank); } if (ir & 1) { add({a, b}, r - (1 << rank), r, --ir); r -= (1 << rank); } rank++; il >>= 1; ir >>= 1; } } T min(T x) { int k = get_index(x) + sz; T val = std::numeric_limits<T>::max(); while (k > 0) { val = std::min(val, f(data[k], x)); k >>= 1; } return val; } private: std::vector<std::pair<T, T>> data; std::vector<T> xs; int sz; }; } // namespace ebi #line 2 "template/int_alias.hpp" #include <cstdint> namespace ebi { using ld = long double; using std::size_t; using i8 = std::int8_t; using u8 = std::uint8_t; using i16 = std::int16_t; using u16 = std::uint16_t; using i32 = std::int32_t; using u32 = std::uint32_t; using i64 = std::int64_t; using u64 = std::uint64_t; using i128 = __int128_t; using u128 = __uint128_t; } // namespace ebi #line 9 "test/data_structure/Segment_Add_Get_Min.test.cpp" using ebi::i64; int main() { int n, q; std::cin >> n >> q; std::vector<std::pair<i64, i64>> lr(n); std::vector<std::pair<i64, i64>> y(n); std::vector<i64> x; for (int i = 0; i < n; i++) { std::cin >> lr[i].first >> lr[i].second; std::cin >> y[i].first >> y[i].second; } std::vector<std::vector<i64>> query(q); for (int i = 0; i < q; i++) { i64 t; std::cin >> t; query[i].emplace_back(t); if (t == 0) { i64 l, r, a, b; std::cin >> l >> r >> a >> b; query[i].emplace_back(l); query[i].emplace_back(r); query[i].emplace_back(a); query[i].emplace_back(b); } else { i64 p; std::cin >> p; query[i].emplace_back(p); x.emplace_back(p); } } if (x.size() == 0) return 0; std::sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end()); x.emplace_back(1e9 + 10); ebi::li_chao_tree<i64> seg(x); for (int i = 0; i < n; i++) { auto [l, r] = lr[i]; auto [a, b] = y[i]; seg.add_segment(a, b, l, r); } for (int i = 0; i < q; i++) { if (query[i][0] == 0) { i64 l = query[i][1]; i64 r = query[i][2]; i64 a = query[i][3]; i64 b = query[i][4]; seg.add_segment(a, b, l, r); } else { i64 ret = seg.min(query[i][1]); if (ret == std::numeric_limits<i64>::max()) { std::cout << "INFINITY" << std::endl; } else { std::cout << ret << std::endl; } } } }