SHARE
TWEET

Untitled

a guest Jun 18th, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const long long maxk = 1e8 + 113;
  2. const long long maxb = 1e18 + 113;
  3. const long long inf = 2e18;
  4.  
  5. struct line {
  6.     long long k, b;
  7.     line()
  8.     {
  9.         this->k = 0;
  10.         this->b = 0;
  11.     }
  12.     line(long long k, long long b)
  13.     {
  14.         this->k = k;
  15.         this->b = b;
  16.     }
  17.     long long func(long long x)
  18.     {
  19.         return k * x + b;
  20.     }
  21. };
  22.  
  23.  
  24. struct LiChao {
  25.     vector<line> ms;
  26.     vector<int> le, re;
  27.     long long range;
  28.     LiChao() {
  29.         this->range = maxk - 113;
  30.         ms.push_back(line());
  31.         le.push_back(-1);
  32.         re.push_back(-1);
  33.     }
  34.     LiChao(long long range) {
  35.         this->range = range;
  36.         ms.push_back(line());
  37.         le.push_back(-1);
  38.         re.push_back(-1);
  39.     }
  40.     void clear() {
  41.         ms.clear();
  42.         le.clear();
  43.         re.clear();
  44.         ms.push_back(line());
  45.         le.push_back(-1);
  46.         re.push_back(-1);
  47.     }
  48.     void push(int v, bool e)
  49.     {
  50.         if (!e && le[v] == -1)
  51.         {
  52.             le[v] = ms.size();
  53.             ms.push_back(ms[v]);
  54.             le.push_back(-1);
  55.             re.push_back(-1);
  56.         }
  57.         if (e && re[v] == -1)
  58.         {
  59.             re[v] = ms.size();
  60.             ms.push_back(ms[v]);
  61.             le.push_back(-1);
  62.             re.push_back(-1);
  63.         }
  64.     }
  65.     void add(int v, long long l, long long r, line in)
  66.     {
  67.         long long m = (l + r) >> 1;
  68.         if (l > r)
  69.             return;
  70.         if (in.func(m) > ms[v].func(m))
  71.             swap(in, ms[v]);
  72.         if (l == r)
  73.             return;
  74.         if (in.func(l) > ms[v].func(l))
  75.         {
  76.             push(v, 0);
  77.             add(le[v], l, m, in);
  78.         }
  79.         else
  80.         {
  81.             push(v, 1);
  82.             add(re[v], m + 1, r, in);
  83.         }
  84.     }
  85.     void add(line in)
  86.     {
  87.         add(0, -range, range, in);
  88.     }
  89.     long long get(int v, long long l, long long r, long long x)
  90.     {
  91.         if (l >= r)
  92.             return ms[v].func(x);
  93.         long long m = (l + r) >> 1;
  94.         if (x <= m)
  95.         {
  96.             if (le[v] == -1)
  97.                 return ms[v].func(x);
  98.             //push(v, 0);
  99.             return max(get(le[v], l, m, x), ms[v].func(x));
  100.         }
  101.         else
  102.         {
  103.             //push(v, 1);
  104.             if (re[v] == -1)
  105.                 return ms[v].func(x);
  106.             return max(get(re[v], m + 1, r, x), ms[v].func(x));
  107.         }
  108.     }
  109.     long long get(long long x)
  110.     {
  111.         return get(0, -range, range, x);
  112.     }
  113. };
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top