test/line_add_get_min.test.cpp

• View this file on GitHub
• Last update: 2025-05-31 14:45:17+09:00
• Problem: https://judge.yosupo.jp/problem/line_add_get_min

Depends on

• Dynamic Li Chao Tree (data_structure/dynamic_li_chao_tree.hpp)
• math/inf.hpp

Code

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

#include <data_structure/dynamic_li_chao_tree.hpp>  // for DynamicLiChaoTree
#include <fastio/base.hpp>                          // for cin, FASTIO, cout
#include <fastio/char/write.hpp>                    // for operator<<
#include <fastio/signed/read.hpp>                   // for operator>>
#include <fastio/signed/write.hpp>                  // for operator<<
#include <math/inf.hpp>                             // for INF
#include <templates/macro/abbrev/endl.hpp>          // for endl
#include <templates/macro/abbrev/ll.hpp>            // for ll
#include <templates/rep.hpp>                        // for rep
#include <templates/template.hpp>
#include <version>  // for std

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    DynamicLiChaoTree<ll, -1000000001, 1000000001, []() -> ll { return Infinite{}; }> tree;
    rep(_, n) {
        ll a, b;
        cin >> a >> b;
        tree.add(a, b);
    }
    rep(_, q) {
        int T;
        cin >> T;
        if (T == 0) {
            ll a, b;
            cin >> a >> b;
            tree.add(a, b);
        } else {
            ll p;
            cin >> p;
            cout << tree(p) << endl;
        }
    }
}

#line 1 "test/line_add_get_min.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/line_add_get_min"

#include <data_structure/dynamic_li_chao_tree.hpp>  // for DynamicLiChaoTree
#include <fastio/base.hpp>                          // for cin, FASTIO, cout
#include <fastio/char/write.hpp>                    // for operator<<
#include <fastio/signed/read.hpp>                   // for operator>>
#include <fastio/signed/write.hpp>                  // for operator<<
#include <math/inf.hpp>                             // for INF
#include <templates/macro/abbrev/endl.hpp>          // for endl
#include <templates/macro/abbrev/ll.hpp>            // for ll
#include <templates/rep.hpp>                        // for rep
#include <templates/template.hpp>
#include <version>  // for std

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    DynamicLiChaoTree<ll, -1000000001, 1000000001, []() -> ll { return Infinite{}; }> tree;
    rep(_, n) {
        ll a, b;
        cin >> a >> b;
        tree.add(a, b);
    }
    rep(_, q) {
        int T;
        cin >> T;
        if (T == 0) {
            ll a, b;
            cin >> a >> b;
            tree.add(a, b);
        } else {
            ll p;
            cin >> p;
            cout << tree(p) << endl;
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	17 ms	4 MB
g++	half_00	AC	304 ms	10 MB
g++	hand_max_00	AC	231 ms	23 MB
g++	max_random_00	AC	43 ms	17 MB
g++	max_random_01	AC	43 ms	17 MB
g++	max_random_02	AC	43 ms	17 MB
g++	no_output_00	AC	35 ms	18 MB
g++	parabola_random_00	AC	238 ms	26 MB
g++	parabola_random_01	AC	239 ms	26 MB
g++	parabola_random_02	AC	239 ms	26 MB
g++	random_00	AC	32 ms	14 MB
g++	random_01	AC	34 ms	14 MB
g++	random_02	AC	23 ms	11 MB
g++	small_00	AC	5 ms	4 MB
g++	small_01	AC	5 ms	4 MB

Back to top page