This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub kmyk/competitive-programming-library
#define PROBLEM "https://judge.yosupo.jp/problem/segment_add_get_min"
#include "../data_structure/li_chao_tree.hpp"
#include "../utils/macros.hpp"
#include <cstdio>
#include <climits>
#include <tuple>
#include <vector>
using namespace std;
int main() {
// input
int n, q; scanf("%d%d", &n, &q);
vector<int64_t> xs;
vector<tuple<int64_t, int64_t, int64_t, int64_t> > segments;
REP (i, n) {
int64_t l, r, a, b; scanf("%lld%lld%lld%lld", &l, &r, &a, &b);
xs.push_back(l);
xs.push_back(r);
segments.emplace_back(l, r, a, b);
}
vector<tuple<int, int64_t, int64_t, int64_t, int64_t, int64_t> > queries;
REP (j, q) {
int t; scanf("%d", &t);
if (t == 0) {
int64_t l, r, a, b; scanf("%lld%lld%lld%lld", &l, &r, &a, &b);
xs.push_back(l);
xs.push_back(r);
queries.emplace_back(t, l, r, a, b, -1);
} else if (t == 1) {
int64_t p; scanf("%lld", &p);
xs.push_back(p);
queries.emplace_back(t, -1, -1, -1, -1, p);
} else {
assert (false);
}
}
// construct
sort(ALL(xs));
xs.erase(unique(ALL(xs)), xs.end());
li_chao_tree lichao(xs);
// output
for (auto [l, r, a, b] : segments) {
lichao.add_segment(l, r, a, b);
}
for (auto [t, l, r, a, b, p] : queries) {
if (t == 0) {
lichao.add_segment(l, r, a, b);
} else if (t == 1) {
int64_t q = lichao.get_min(p);
if (q == INT64_MAX) {
printf("INFINITY\n");
} else {
printf("%lld\n", q);
}
} else {
assert (false);
}
}
return 0;
}
#line 1 "data_structure/li_chao_tree.segment_add_get_min.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/segment_add_get_min"
#line 2 "data_structure/li_chao_tree.hpp"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>
#line 2 "utils/macros.hpp"
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
#line 8 "data_structure/li_chao_tree.hpp"
/**
* @brief Li-Chao tree
* @docs data_structure/li_chao_tree.md
*/
struct li_chao_tree {
int k;
std::vector<std::pair<int64_t, int64_t> > f;
std::vector<int64_t> x;
std::vector<int64_t> y;
li_chao_tree() = default;
li_chao_tree(const std::vector<int64_t> & x_) : x(x_) {
assert (std::is_sorted(ALL(x)));
k = 0; while ((1 << k) < x.size()) ++ k;
f.resize((1 << k) - 1, std::make_pair(0, std::numeric_limits<int64_t>::max()));
y.resize(x.size(), std::numeric_limits<int64_t>::max());
}
/**
* @note i is a point on the original space
*/
int64_t get_min(int64_t i) {
i = std::lower_bound(ALL(x), i) - x.begin();
return get_min_compressed(i);
}
int64_t get_min_compressed(int i) { // 0-based
assert (0 <= i and i < x.size());
int64_t z = y[i];
for (int j = (i + (1 << k)) / 2; j > 0; j /= 2) { // 1-based
z = std::min(z, f[j - 1].first * x[i] + f[j - 1].second);
}
return z;
}
/**
* @note [l, r) is an interval on the original space
*/
void add_segment(int64_t l, int64_t r, int64_t a, int64_t b) {
l = std::lower_bound(ALL(x), l) - x.begin();
r = std::lower_bound(ALL(x), r) - x.begin();
add_segment_compressed(l, r, a, b);
}
void add_segment_compressed(int64_t l, int64_t r, int64_t a, int64_t b) {
assert (0 <= l and l <= r and r <= x.size());
add_segment_compressed(0, 0, 1 << k, l, r, a, b);
}
void add_segment_compressed(int i, int il, int ir, int l, int r, int64_t a, int64_t b) {
if (l <= il and ir <= r) { // 0-based
if (i >= (1 << k) - 1) {
int j = i - (1 << k) + 1;
y[j] = std::min(y[j], a * x[j] + b);
} else {
int64_t xl = x[il];
int64_t xr = x[ir - 1]; // [xl, xr]
int64_t yl1 = f[i].first * xl + f[i].second;
int64_t yr1 = f[i].first * xr + f[i].second;
int64_t yl2 = a * xl + b;
int64_t yr2 = a * xr + b;
if (yl1 <= yl2 and yr1 <= yr2) {
// if forall x in [l, r]. f(x) <= g(x), then do nothing
// nop
} else if (yl2 <= yl1 and yr2 <= yr1) {
// if forall x in [l, r]. g(x) <= f(x), then replace f with g
f[i] = std::make_pair(a, b);
} else {
int64_t xm = x[(il + ir) / 2];
int64_t ym1 = f[i].first * xm + f[i].second;
int64_t ym2 = a * xm + b;
if (yl1 <= yl2 and ym1 <= ym2) {
// if forall x in [l, m]. f(x) <= g(x), then do recursion for [m, r] with f
add_segment_compressed(2 * i + 2, (il + ir) / 2, ir, l, r, a, b);
} else if (yl2 <= yl1 and ym2 <= ym1) {
// if forall x in [l, m]. g(x) <= f(x), then replace f with g and do recursion for [m, r] with g
std::swap(a, f[i].first);
std::swap(b, f[i].second);
add_segment_compressed(2 * i + 2, (il + ir) / 2, ir, l, r, a, b);
} else if (ym1 <= ym2 and yr1 <= yr2) {
// if forall x in [m, r]. f(x) <= g(x), then do recursion for [l, m] with f
add_segment_compressed(2 * i + 1, il, (il + ir) / 2, l, r, a, b);
} else if (ym2 <= ym1 and yr2 <= yr1) {
// if forall x in [m, r]. g(x) <= f(x), then replace f with g and do recursion for [l, m] with g
std::swap(a, f[i].first);
std::swap(b, f[i].second);
add_segment_compressed(2 * i + 1, il, (il + ir) / 2, l, r, a, b);
} else {
assert (false);
}
}
}
} else if (ir <= l or r <= il) {
// nop
} else {
add_segment_compressed(2 * i + 1, il, (il + ir) / 2, l, r, a, b);
add_segment_compressed(2 * i + 2, (il + ir) / 2, ir, l, r, a, b);
}
}
};
#line 4 "data_structure/li_chao_tree.segment_add_get_min.test.cpp"
#include <cstdio>
#include <climits>
#include <tuple>
#line 8 "data_structure/li_chao_tree.segment_add_get_min.test.cpp"
using namespace std;
int main() {
// input
int n, q; scanf("%d%d", &n, &q);
vector<int64_t> xs;
vector<tuple<int64_t, int64_t, int64_t, int64_t> > segments;
REP (i, n) {
int64_t l, r, a, b; scanf("%lld%lld%lld%lld", &l, &r, &a, &b);
xs.push_back(l);
xs.push_back(r);
segments.emplace_back(l, r, a, b);
}
vector<tuple<int, int64_t, int64_t, int64_t, int64_t, int64_t> > queries;
REP (j, q) {
int t; scanf("%d", &t);
if (t == 0) {
int64_t l, r, a, b; scanf("%lld%lld%lld%lld", &l, &r, &a, &b);
xs.push_back(l);
xs.push_back(r);
queries.emplace_back(t, l, r, a, b, -1);
} else if (t == 1) {
int64_t p; scanf("%lld", &p);
xs.push_back(p);
queries.emplace_back(t, -1, -1, -1, -1, p);
} else {
assert (false);
}
}
// construct
sort(ALL(xs));
xs.erase(unique(ALL(xs)), xs.end());
li_chao_tree lichao(xs);
// output
for (auto [l, r, a, b] : segments) {
lichao.add_segment(l, r, a, b);
}
for (auto [t, l, r, a, b, p] : queries) {
if (t == 0) {
lichao.add_segment(l, r, a, b);
} else if (t == 1) {
int64_t q = lichao.get_min(p);
if (q == INT64_MAX) {
printf("INFINITY\n");
} else {
printf("%lld\n", q);
}
} else {
assert (false);
}
}
return 0;
}