daily pastebin goal
3%
SHARE
TWEET

Li Chao Min

a guest Dec 10th, 2018 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //we assume here n = 1e6, use limits appropriate to the problem
  2. struct Line //mx + b
  3. {
  4.     ll m;
  5.     ll b;
  6.     ld f(ld x)
  7.     {
  8.         return m*x + b;
  9.     }
  10. };
  11.  
  12. ll f(Line L, ll x)
  13. {
  14.     return L.m*x + L.b;
  15. }
  16.  
  17. Line tr[4000000];
  18. struct CHT_MIN //lichao tree
  19. {
  20.     void build(int lo = 1, int hi = 1e6+1, int cur = 1)
  21.     {
  22.         if (tr[cur].m == 0 && tr[cur].b == INF) return;
  23.         tr[cur] = {0, INF};
  24.         if (hi-lo == 1) return;
  25.         int mid = (lo+hi)/2;
  26.         build(lo, mid, cur*2);
  27.         build(mid, hi, cur*2+1);
  28.     }
  29.     void upd(Line L, int lo = 1, int hi = 1e6+1, int cur = 1)
  30.     {
  31.         int mid = (lo+hi)/2;
  32.         ll optMid = L.f(mid) < tr[cur].f(mid);
  33.         ll optLow = L.f(lo ) < tr[cur].f(lo );
  34.         if (optMid) swap(L, tr[cur]);
  35.         if (hi-lo == 1) return;
  36.         if (optMid != optLow) upd(L, lo, mid, cur*2);
  37.         else upd(L, mid, hi, cur*2+1);
  38.     }
  39.     ll get(int x, int lo = 1, int hi = 1e6+1, int cur = 1)
  40.     {
  41.         int mid = (lo+hi)/2;
  42.         ll val = f(tr[cur], x);
  43.         if (hi-lo == 1) return val;
  44.         if (x < mid) return min(val, get(x, lo, mid, cur*2));
  45.         else return min(val, get(x, mid, hi, cur*2+1));
  46.     }
  47. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top