This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub crackersamdjam/Codebook
#define PROBLEM "https://judge.yosupo.jp/problem/line_add_get_min" #include "../content/data_structures/li_chao_tree.h" int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit); int n, q; cin>>n>>q; sparse_li_chao_tree<ll> st; st.init(-1e9, 1e9, LLONG_MAX, [](auto x, auto y){ return min(x, y); }); while(n--){ ll a, b; cin>>a>>b; st.add({a, b}); } while(q--){ int op; cin>>op; if(op == 0){ ll a, b; cin>>a>>b; st.add({a, b}); } else{ ll x; cin>>x; cout<<st.get(x)<<'\n'; } } }
#line 1 "tests/li_chao_tree.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/line_add_get_min" #line 1 "content/utils/template.h" /** * @brief My starter code */ #include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define makeunique(x) (x).erase(unique((x).begin(), (x).end()), (x).end()); #ifdef LOCAL template<typename T> void pr(T a){std::cerr<<a<<std::endl;} template<typename T, typename... Args> void pr(T a, Args... args){std::cerr<<a<<' ',pr(args...);} #else template<typename... Args> void pr(Args... args){} #endif using namespace std; using ll = long long; using pii = pair<int, int>; #line 3 "content/data_structures/li_chao_tree.h" /** * @brief Li Chao Tree * @docs docs/li_chao_tree.md */ template<typename T> struct line{ T m, b; T eval(T x){ return m*x + b;} }; template<typename T> struct sparse_li_chao_tree{ int LS, RS; T def; function<T(T, T)> merge; struct node{ node *lc, *rc; line<T> val; node(line<T> _val){ lc = rc = nullptr; val = _val; } }; node *rt = nullptr; // merge() should be min or max void init(int _LS, int _RS, T _def, function<T(T, T)> _merge){ LS = _LS; RS = _RS; def = _def; merge = _merge; } #define nm (nl+(nr-nl)/2) // this works for negative indices too, unlike (nl+nr)/2 void _add(line<T> ln, int nl, int nr, node *&cur){ assert(nl <= nr); if(!cur){ cur = new node(ln); return; } bool bl = ln.eval(nl) < cur->val.eval(nl); bool bm = ln.eval(nm) < cur->val.eval(nm); if(bm) swap(cur->val, ln); if(nl == nr) return; bl != bm ? _add(ln, nl, nm, cur->lc) : _add(ln, nm+1, nr, cur->rc); } void add(line<T> ln){ _add(ln, LS, RS, rt); } T _get(T x, int nl, int nr, node *cur){ if(!cur) return def; if(nl == nr) return cur->val.eval(x); if(x <= nm) return merge(cur->val.eval(x), _get(x, nl, nm, cur->lc)); return merge(cur->val.eval(x), _get(x, nm+1, nr, cur->rc)); } T get(T x){ return _get(x, LS, RS, rt); } #undef nm }; #line 3 "tests/li_chao_tree.test.cpp" int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit); int n, q; cin>>n>>q; sparse_li_chao_tree<ll> st; st.init(-1e9, 1e9, LLONG_MAX, [](auto x, auto y){ return min(x, y); }); while(n--){ ll a, b; cin>>a>>b; st.add({a, b}); } while(q--){ int op; cin>>op; if(op == 0){ ll a, b; cin>>a>>b; st.add({a, b}); } else{ ll x; cin>>x; cout<<st.get(x)<<'\n'; } } }