Original link: https://www.shuizilong.com/house/archives/jsoi2008blue-mary%E5%BC%80%E5%85%AC%E5%8F%B8/
This is awesome. . .
#define ll double struct Line { mutable ll k, b, p; Line (ll k = 0, ll b = 0):k(k),b(b){ p = 0; } ll y(ll x) const {return k*x + b;} bool operator<(const Line& o) const { return k < ok; } bool operator<(ll x) const { return p < x; } }; struct LineContainer : multiset<Line,less<>> { const ll inf = 1/.0; ll div(ll a, ll b) { return a / b; } bool isect(iterator x, iterator y) { if (y == end()) return x->p = inf, 0; if (x->k == y->k) x->p = x->b > y->b ? inf : -inf; else x->p = div(y->b - x->b, x->k - y->k); return x->p >= y->p; } void add(ll k, ll b) { add(Line(k,b)); } void add(Line t) { auto z = insert(t), y = z++, x = y; while (isect(y, z)) z = erase(z); if (x != begin() && isect(--x, y)) isect(x, y = erase(y)); while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y)); } ll query(ll x) { assert(!empty()); auto& l = *lower_bound(x); return ly(x); } } H; int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); #endif H.add(0, 0); char cmd[10]; DB k, b, x; Rush { RS(cmd); if (cmd[0] == 'P') { RF(b, k); H.add(k, b); } else { RF(x); OT(LL(H.query(x-1)/100)); } } }
This article is reproduced from: https://www.shuizilong.com/house/archives/jsoi2008blue-mary%E5%BC%80%E5%85%AC%E5%8F%B8/
This site is for inclusion only, and the copyright belongs to the original author.