Submit Info #2615

Problem Lang User Status Time Memory
Line Add Get Min cpp14 face4 AC 585 ms 21.30 MiB

ケース詳細
Name Status Time Memory
example_00 AC 7 ms 0.55 MiB
half_00 AC 368 ms 9.38 MiB
hand_max_00 AC 585 ms 21.30 MiB
max_random_00 AC 448 ms 14.75 MiB
max_random_01 AC 452 ms 14.73 MiB
max_random_02 AC 454 ms 14.72 MiB
parabola_random_00 AC 502 ms 14.55 MiB
parabola_random_01 AC 499 ms 14.51 MiB
parabola_random_02 AC 490 ms 14.52 MiB
random_00 AC 312 ms 12.13 MiB
random_01 AC 330 ms 12.45 MiB
random_02 AC 214 ms 7.61 MiB
small_00 AC 6 ms 0.64 MiB
small_01 AC 6 ms 0.67 MiB

#include<iostream> #include<vector> #include<algorithm> using namespace std; typedef long long ll; struct line{ ll a, b; bool operator==(const line other)const{ return a==other.a && b==other.b; } }; ll f(line l, ll x){ return l.a*x + l.b; } const ll INF = 1ll<<55; struct LiChaoTree{ int n; vector<ll> xs; vector<line> v; line tmp{0, INF}; LiChaoTree(vector<ll> x) : xs(x){ n = 1; while(n < xs.size()) n *= 2; while(xs.size() < n) xs.push_back(x.back()); v.resize(2*n+1, tmp); } void add_line(line p, int k=0, int l=0, int r=-1){ if(r < 0) r = n; int m = (l+r)/2; if(v[k] == tmp){ v[k] = p; return; } ll lx = xs[l], mx = xs[m], rx = xs[r-1]; bool left = f(p,lx) < f(v[k], lx); bool mid = f(p,mx) < f(v[k], mx); bool right = f(p,rx) < f(v[k], rx); if(left == right){ if(left) v[k] = p; return; } if(mid){ swap(v[k], p); } // v[k]とpが交わっている部分について更新していくと考えるとわかりやすい if(left != mid){ add_line(p, 2*k+1, l, m); }else{ add_line(p, 2*k+2, m, r); } } ll query(int k){ ll x = xs[k]; k += n-1; ll ret = INF; while(true){ if(!(v[k]==tmp)) ret = min(ret, f(v[k], x)); if(k==0) break; k = (k-1)/2; } return ret; } }; int main(){ int n, q; cin >> n >> q; vector<ll> a(n+q), b(n+q); for(int i = 0; i < n; i++) cin >> a[i] >> b[i]; vector<ll> v; vector<bool> query(q, 0); for(int i = 0; i < q; i++){ int op; cin >> op; if(op == 0){ cin >> a[n+i] >> b[n+i]; }else{ query[i] = true; cin >> a[n+i]; v.push_back(a[n+i]); } } sort(v.begin(), v.end()); v.erase(unique(v.begin(),v.end()),v.end()); int siz = v.size(); LiChaoTree lct(v); auto f = [&](int x)->int{ return lower_bound(v.begin(),v.end(),x)-v.begin(); }; for(int i = 0; i < n; i++) lct.add_line(line({a[i], b[i]})); for(int i = 0; i < q; i++){ if(query[i]) cout << lct.query(f(a[n+i])) << endl; else lct.add_line(line({a[n+i], b[n+i]})); } return 0; }