[Codechef] POLY - Polynomials

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : POLY - Polynomials 
Source            : Codeforces
Category          : Data Structure
Algorithm         : Li Chao Tree
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 2e5 + 5;  
static const int offset = 350; // Bruteforce for this limit  
static const long long inf = 1e18;  
  
struct Line  
{  
      long long a;  
      long long b;  
      long long c;  
      long long d;  
  
      Line(long long a = inf, long long b = 0, long long c = 0, long long d = 0)  
            : a(a)  
            , b(b)  
            , c(c)  
            , d(d) {}  
  
      long long evalute(long long x)  
      {  
            return a + b * x + c * x * x + d * x * x * x;  
      }  
} Tree[maxn * 4];  
  
int N = 1e5; // Maximum Query Points  
long long aux[offset + 5];  
  
void init()  
{  
      for (int i = 0; i < offset; i++) aux[i] = inf;  
      for (int i = 0; i < maxn * 4; i++) Tree[i] = Line();  
}  
  
int compare(long long x, long long y)  
{  
      if (x < y) return -1;  
      return x > y;  
}  
  
void update(int node, int a, int b, int i, int j, Line fx)  
{  
      if (a > j or b < i) return;  
      int lchild = node * 2;  
      int rchild = lchild + 1;  
      int mid = (a + b) / 2;  
      if (a >= i and b <= j)  
      {  
            // fx         = new function  
            // Tree[node] = old function  
  
            int fa = compare(fx.evalute(a), Tree[node].evalute(a));  
            int fb = compare(fx.evalute(b), Tree[node].evalute(b));  
            int fm1 = compare(fx.evalute(mid), Tree[node].evalute(mid));  
            int fm2 = compare(fx.evalute(mid + 1), Tree[node].evalute(mid + 1));  
  
            // New function is worse for a to b, no point of adding it  
            if (fa >= 0 and fb >= 0) return;  
  
            // New function is better for a to b, add it  
            if (fa <= 0 and fb <= 0)  
            {  
                  Tree[node] = fx;  
                  return;  
            }  
  
            // New function is better for a to mid, add it. Old function can still be  
            // better for right segment.  
            if (fa <= 0 and fm1 <= 0)  
            {  
                  // Sending the old function to the right segment  
                  update(rchild, mid + 1, b, i, j, Tree[node]);  
                  Tree[node] = fx;  
                  return;  
            }  
  
            // New function is worse for a to mid, but this can be better for right segment.  
            if (fa >= 0 and fm1 >= 0)  
            {  
                  update(rchild, mid + 1, b, i, j, fx);  
                  return;  
            }  
  
            // New function worse for mid + 1 to b, but can be better for left segment  
            if (fm2 >= 0 and fb >= 0)  
            {  
                  update(lchild, a, mid, i, j, fx);  
                  return;  
            }  
  
            // New function better for mid + 1 to b, add it. Old function can still be better  
            // for left.  
            if (fm2 <= 0 and fb <= 0)  
            {  
                  update(lchild, a, mid, i, j, Tree[node]);  
                  Tree[node] = fx;  
                  return;  
            }  
      }  
      else if (a < b)  
      {  
            update(lchild, a, mid, i, j, fx);  
            update(rchild, mid + 1, b, i, j, fx);  
      }  
}  
  
long long query(int node, int a, int b, long long x)  
{  
      if (a == b) return Tree[node].evalute(x);  
      int lchild = node * 2;  
      int rchild = lchild + 1;  
      int mid = (a + b) / 2;  
      long long ret = Tree[node].evalute(x);  
      if (x <= mid) ret = min(ret, query(lchild, a, mid, x));  
      else ret = min(ret, query(rchild, mid + 1, b, x));  
      return ret;  
}  
  
void calc(Line fx)  
{  
      for (int x = 0; x < offset; x++)  
      {  
            aux[x] = min(aux[x], fx.evalute(x));  
      }  
}  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      int tc;  
      cin >> tc;  
      for (int tcase = 1; tcase <= tc; tcase++)  
      {  
            int n;  
            cin >> n;  
            init();  
            for (int i = 0; i < n; i++)  
            {  
                  Line fx;  
                  cin >> fx.a >> fx.b >> fx.c >>  fx.d;  
                  calc(fx);  
                  update(1, 1, N, offset, N, fx);  
            }  
            int q;  
            cin >> q;  
            while (q--)  
            {  
                  long long x;  
                  cin >> x;  
                  long long minval;  
                  if (x < offset) minval = aux[x];  
                  else minval = query(1, 1, N, x);  
                  cout << minval << '\n';  
            }  
      }  
}