cpp_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub toyama1710/cpp_library

:heavy_check_mark: test/yosupo/segment_add_get_min.test.cpp

Depends on

Code

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

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

#include "../../cht/li_chao_tree.hpp"

using namespace std;
using llong = long long;

llong n, q;
vector<tuple<llong, llong, llong, llong, llong>> query;
vector<llong> l, r;
vector<llong> a, b;
vector<llong> p;

int main() {
    cin >> n >> q;
    l.resize(n);
    r.resize(n);
    a.resize(n);
    b.resize(n);
    query.resize(q);
    for (int i = 0; i < n; i++) {
        cin >> l[i] >> r[i] >> a[i] >> b[i];
        p.push_back(l[i]);
        p.push_back(r[i]);
    }

    for (int i = 0; i < q; i++) {
        llong com, l, r, a, b;

        cin >> com;
        if (com == 0) {
            cin >> l >> r >> a >> b;
            p.push_back(l);
            p.push_back(r);
        } else {
            cin >> l;
            p.push_back(l);
        }
        query[i] = tie(com, l, r, a, b);
    }

    LiChaoTree<llong> cht(p);
    for (int i = 0; i < n; i++) {
        cht.add_segment(a[i], b[i], l[i], r[i]);
    }

    for (int i = 0; i < q; i++) {
        llong com, l, r, a, b;
        tie(com, l, r, a, b) = query[i];

        if (com == 0) {
            cht.add_segment(a, b, l, r);
        } else {
            auto out = cht.get(l);

            if (out >= llong(1e18) * 3) {
                cout << "INFINITY" << '\n';
            } else {
                cout << out << '\n';
            }
        }
    }

    return 0;
};
#line 1 "test/yosupo/segment_add_get_min.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/segment_add_get_min"

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

#line 1 "cht/li_chao_tree.hpp"



#line 5 "cht/li_chao_tree.hpp"
#include <iterator>
#include <limits>
#include <numeric>
#line 9 "cht/li_chao_tree.hpp"

template <class T = long long>
struct LiChaoTree {
    struct Line {
        T a, b;
        Line(T a, T b) : a(a), b(b){};
        T get(T x) {
            return a * x + b;
        };
        inline static Line identity() {
            return Line(0, std::numeric_limits<T>::max());
        };
    };

    std::vector<Line> seg;
    std::vector<T> pos;

    LiChaoTree() = default;
    explicit LiChaoTree(int n) {
        int n_ = 1;
        while (n_ < n) n_ *= 2;
        seg.resize(n_ * 2, Line::identity());
        pos.resize(n_);
        std::iota(pos.begin(), pos.end(), T(0));
    };

    template <class InputItr>
    LiChaoTree(InputItr first, InputItr last) {
        init(first, last);
    };

    LiChaoTree(std::vector<T> p) {
        std::sort(p.begin(), p.end());
        p.erase(std::unique(p.begin(), p.end()), p.end());
        init(p.begin(), p.end());
    };

    template <class InputItr>
    void init(InputItr first, InputItr last) {
        int n = std::distance(first, last);
        int n_ = 1;

        while (n_ < n) n_ *= 2;

        seg.resize(n_ * 2, Line::identity());
        pos.reserve(n_);
        for (; first != last; first++) pos.push_back(*first);
        while (pos.size() < n_) pos.push_back(pos.back() + 1);
    }

    int size() {
        return seg.size() >> 1;
    };

    void add_line(T a, T b) {
        update(Line(a, b), 1, 0, size() - 1);
    };

    // [s, t)
    void add_segment(T a, T b, T s, T t) {
        Line x(a, b);
        int sl, tl;
        int len = 1;

        sl = std::lower_bound(pos.begin(), pos.end(), s) - pos.begin();
        tl = std::lower_bound(pos.begin(), pos.end(), t) - pos.begin();

        s = std::lower_bound(pos.begin(), pos.end(), s) - pos.begin() + size();
        t = std::lower_bound(pos.begin(), pos.end(), t) - pos.begin() + size();

        while (s < t) {
            if (s & 1) {
                update(x, s, sl, sl + len - 1);
                sl += len;
                s++;
            }
            if (t & 1) {
                t--;
                tl -= len;
                update(x, t, tl, tl + len - 1);
            }
            s >>= 1;
            t >>= 1;
            len <<= 1;
        }
    };

    // [l, r]
    void update(Line x, int k, int l, int r) {
        T pl = pos[l];
        T pr = pos[r];
        T pm = pos[(l + r) / 2];

        if (x.get(pl) >= seg[k].get(pl) && x.get(pr) >= seg[k].get(pr)) return;

        if (x.get(pl) <= seg[k].get(pl) && x.get(pr) <= seg[k].get(pr)) {
            seg[k] = x;
            return;
        }

        if (x.get(pm) < seg[k].get(pm)) std::swap(x, seg[k]);
        if (x.get(pl) <= seg[k].get(pl))
            update(x, k << 1, l, (l + r) / 2);
        else
            update(x, (k << 1) | 1, (l + r) / 2 + 1, r);
    };

    T get(T x) {
        int k =
            std::lower_bound(pos.begin(), pos.end(), x) - pos.begin() + size();

        T ret = seg[k].get(x);
        while (k > 0) {
            k >>= 1;
            ret = std::min(ret, seg[k].get(x));
        }
        return ret;
    };
};


#line 9 "test/yosupo/segment_add_get_min.test.cpp"

using namespace std;
using llong = long long;

llong n, q;
vector<tuple<llong, llong, llong, llong, llong>> query;
vector<llong> l, r;
vector<llong> a, b;
vector<llong> p;

int main() {
    cin >> n >> q;
    l.resize(n);
    r.resize(n);
    a.resize(n);
    b.resize(n);
    query.resize(q);
    for (int i = 0; i < n; i++) {
        cin >> l[i] >> r[i] >> a[i] >> b[i];
        p.push_back(l[i]);
        p.push_back(r[i]);
    }

    for (int i = 0; i < q; i++) {
        llong com, l, r, a, b;

        cin >> com;
        if (com == 0) {
            cin >> l >> r >> a >> b;
            p.push_back(l);
            p.push_back(r);
        } else {
            cin >> l;
            p.push_back(l);
        }
        query[i] = tie(com, l, r, a, b);
    }

    LiChaoTree<llong> cht(p);
    for (int i = 0; i < n; i++) {
        cht.add_segment(a[i], b[i], l[i], r[i]);
    }

    for (int i = 0; i < q; i++) {
        llong com, l, r, a, b;
        tie(com, l, r, a, b) = query[i];

        if (com == 0) {
            cht.add_segment(a, b, l, r);
        } else {
            auto out = cht.get(l);

            if (out >= llong(1e18) * 3) {
                cout << "INFINITY" << '\n';
            } else {
                cout << out << '\n';
            }
        }
    }

    return 0;
};
Back to top page