[Codechef] DIVMAC - Dividing Machine

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : DIVMAC - Dividing Machine
Source            : Codechef
Category          : Number Theory, Data Structure
Algorithm         : Sieve - Smallest Prime Factor, Segment Tree
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll           long long int   
#define endl         '\n'  
  
static const int maxn = 2e6 + 5;  
  
bool isprime[maxn];  
vector <int> prime;  
int sp[maxn];  
  
void sieve()  
{  
    for (int i = 2; i < maxn; i++) isprime[i] = true;  
    sp[2] = 2;  
    for (int i = 4; i < maxn; i += 2) isprime[i] = false, sp[i] = 2;  
    for (long long i = 3; i < maxn; i += 2)  
    {  
        if (isprime[i])  
        {  
            sp[i] = i;  
            for (long long j = i; i * j < maxn; j += 2)  
            {  
                if (isprime[i * j])  
                {  
                    isprime[i * j] = false;  
                    sp[i * j] = i;  
                }  
            }  
        }  
    }  
    prime.push_back(2);  
    for (int i = 3; i < maxn; i += 2) if (isprime[i]) prime.push_back(i);  
}  
  
struct SegmentTree  
{  
    int num;  
    int lpf;  
    SegmentTree(int num = 0, int lpf = 0) : num(num), lpf(lpf) {}  
      
    void assignLeaf(int x, int y)  
    {  
        num = x;  
        lpf = y;  
    }  
    void marge(const SegmentTree &lchild, const SegmentTree &rchild)  
    {  
        num = max(lchild.num, rchild.num);  
        lpf = max(lchild.lpf, rchild.lpf);  
    }  
} Tree[maxn * 4];  
  
int arr[maxn];  
  
void build(int node, int a, int b)  
{  
    if (a == b) return void(Tree[node].assignLeaf(arr[a], sp[ arr[a] ]));  
    int lchild = node * 2;  
    int rchild = lchild + 1;  
    int mid = (a + b) / 2;  
    build(lchild, a, mid);  
    build(rchild, mid + 1, b);  
    Tree[node].marge(Tree[lchild], Tree[rchild]);  
}  
  
void update(int node, int a, int b, int i, int j)  
{  
    if (a > j or b < i) return;  
    if (a == b)   
    {  
        int num = Tree[node].num / sp[ Tree[node].num ];  
        int lpf = max(1, sp[num]);  
        Tree[node].assignLeaf(num, lpf);  
        return;  
    }  
    int lchild = node * 2;  
    int rchild = lchild + 1;  
    int mid = (a + b) / 2;  
    if (Tree[lchild].num >= 2) update(lchild, a, mid, i, j);  
    if (Tree[rchild].num >= 2) update(rchild, mid + 1, b, i, j);  
    Tree[node].marge(Tree[lchild], Tree[rchild]);  
}  
  
int query(int node, int a, int b, int i, int j)  
{  
    if (a > j or b < i) return 1;  
    if (a >= i and b <= j) return Tree[node].lpf;  
    int lchild = node * 2;  
    int rchild = lchild + 1;  
    int mid = (a + b) / 2;  
    int p = query(lchild, a, mid, i, j);  
    int q = query(rchild, mid + 1, b, i, j);  
    return max(p, q);   
}  
  
signed main()  
{  
    ios_base::sync_with_stdio(false);  
    cin.tie(nullptr);  
    cout.tie(nullptr);  
      
    sieve();  
      
    int tc;  
    cin >> tc;  
    while (tc--)  
    {  
        int n, m;  
        cin >> n >> m;  
        for (int i = 1; i <= n; i++) cin >> arr[i];  
        build(1, 1, n);  
        while (m--)  
        {  
            int type, l, r;  
            cin >> type >> l >> r;  
            if (type == 0) update(1, 1, n, l, r);  
            else cout << query(1, 1, n, l, r) << ' ';  
            for (int i = 1; i <= n; i++) cerr << query(1, 1, n, i, i) << ", ";  
            cerr << endl;  
        }  
        cout << endl;  
    }  
}  

[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';  
            }  
      }  
}