Friday, February 7, 2020

[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

  1. #include "bits/stdc++.h"  
  2.   
  3. using namespace std;  
  4.   
  5. #define ll           long long int   
  6. #define endl         '\n'  
  7.   
  8. static const int maxn = 2e6 + 5;  
  9.   
  10. bool isprime[maxn];  
  11. vector <int> prime;  
  12. int sp[maxn];  
  13.   
  14. void sieve()  
  15. {  
  16.     for (int i = 2; i < maxn; i++) isprime[i] = true;  
  17.     sp[2] = 2;  
  18.     for (int i = 4; i < maxn; i += 2) isprime[i] = false, sp[i] = 2;  
  19.     for (long long i = 3; i < maxn; i += 2)  
  20.     {  
  21.         if (isprime[i])  
  22.         {  
  23.             sp[i] = i;  
  24.             for (long long j = i; i * j < maxn; j += 2)  
  25.             {  
  26.                 if (isprime[i * j])  
  27.                 {  
  28.                     isprime[i * j] = false;  
  29.                     sp[i * j] = i;  
  30.                 }  
  31.             }  
  32.         }  
  33.     }  
  34.     prime.push_back(2);  
  35.     for (int i = 3; i < maxn; i += 2) if (isprime[i]) prime.push_back(i);  
  36. }  
  37.   
  38. struct SegmentTree  
  39. {  
  40.     int num;  
  41.     int lpf;  
  42.     SegmentTree(int num = 0, int lpf = 0) : num(num), lpf(lpf) {}  
  43.       
  44.     void assignLeaf(int x, int y)  
  45.     {  
  46.         num = x;  
  47.         lpf = y;  
  48.     }  
  49.     void marge(const SegmentTree &lchild, const SegmentTree &rchild)  
  50.     {  
  51.         num = max(lchild.num, rchild.num);  
  52.         lpf = max(lchild.lpf, rchild.lpf);  
  53.     }  
  54. } Tree[maxn * 4];  
  55.   
  56. int arr[maxn];  
  57.   
  58. void build(int node, int a, int b)  
  59. {  
  60.     if (a == b) return void(Tree[node].assignLeaf(arr[a], sp[ arr[a] ]));  
  61.     int lchild = node * 2;  
  62.     int rchild = lchild + 1;  
  63.     int mid = (a + b) / 2;  
  64.     build(lchild, a, mid);  
  65.     build(rchild, mid + 1, b);  
  66.     Tree[node].marge(Tree[lchild], Tree[rchild]);  
  67. }  
  68.   
  69. void update(int node, int a, int b, int i, int j)  
  70. {  
  71.     if (a > j or b < i) return;  
  72.     if (a == b)   
  73.     {  
  74.         int num = Tree[node].num / sp[ Tree[node].num ];  
  75.         int lpf = max(1, sp[num]);  
  76.         Tree[node].assignLeaf(num, lpf);  
  77.         return;  
  78.     }  
  79.     int lchild = node * 2;  
  80.     int rchild = lchild + 1;  
  81.     int mid = (a + b) / 2;  
  82.     if (Tree[lchild].num >= 2) update(lchild, a, mid, i, j);  
  83.     if (Tree[rchild].num >= 2) update(rchild, mid + 1, b, i, j);  
  84.     Tree[node].marge(Tree[lchild], Tree[rchild]);  
  85. }  
  86.   
  87. int query(int node, int a, int b, int i, int j)  
  88. {  
  89.     if (a > j or b < i) return 1;  
  90.     if (a >= i and b <= j) return Tree[node].lpf;  
  91.     int lchild = node * 2;  
  92.     int rchild = lchild + 1;  
  93.     int mid = (a + b) / 2;  
  94.     int p = query(lchild, a, mid, i, j);  
  95.     int q = query(rchild, mid + 1, b, i, j);  
  96.     return max(p, q);   
  97. }  
  98.   
  99. signed main()  
  100. {  
  101.     ios_base::sync_with_stdio(false);  
  102.     cin.tie(nullptr);  
  103.     cout.tie(nullptr);  
  104.       
  105.     sieve();  
  106.       
  107.     int tc;  
  108.     cin >> tc;  
  109.     while (tc--)  
  110.     {  
  111.         int n, m;  
  112.         cin >> n >> m;  
  113.         for (int i = 1; i <= n; i++) cin >> arr[i];  
  114.         build(1, 1, n);  
  115.         while (m--)  
  116.         {  
  117.             int type, l, r;  
  118.             cin >> type >> l >> r;  
  119.             if (type == 0) update(1, 1, n, l, r);  
  120.             else cout << query(1, 1, n, l, r) << ' ';  
  121.             for (int i = 1; i <= n; i++) cerr << query(1, 1, n, i, i) << ", ";  
  122.             cerr << endl;  
  123.         }  
  124.         cout << endl;  
  125.     }  
  126. }  

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.