[toph.co] Blackhole and Food

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Blackhole and Food
Source            : toph.co
Category          : Data Structure
Algorithm         : Merge Sort Tree
Verdict           : Accepted
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll                 long long int
 
static const int MAXN = 1e5 + 5;
 
struct information
{
      ll val;
      int id;
      information(ll val = 0, int id = 0) : val(val), id(id) {}
};
 
struct MergeSortTree
{
      vector <information> vec;
      void assignLeaf(ll num, int pos)
      {
            vec.emplace_back(num, pos);
      }
      void MERGE(MergeSortTree &L, MergeSortTree &R)
      {
            int lenL = L.vec.size();
            int lenR = R.vec.size();
            int idL = 0;
            int idR = 0;
            while (idL < lenL && idR < lenR)
            {
                  ll numL = L.vec[idL].val;
                  int posL = L.vec[idL].id;
                  ll numR = R.vec[idR].val;
                  int posR = R.vec[idR].id;
                  if (numL == numR)
                  {
                        if (posL < posR)
                        {
                              vec.push_back(L.vec[idL]);
                              idL++;
                        }
                        else
                        {
                              vec.push_back(R.vec[idR]);
                              idR++;
                        }
                  }
                  else if (numL < numR)
                  {
                        vec.push_back(L.vec[idL]);
                        idL++;
                  }
                  else
                  {
                        vec.push_back(R.vec[idR]);
                        idR++;
                  }
            }
            while (idL < lenL)
            {
                  vec.push_back(L.vec[idL]);
                  idL++;
            }
            while (idR < lenR)
            {
                  vec.push_back(R.vec[idR]);
                  idR++;
            }
      }
 // Binary search
 information BinarySearch(MergeSortTree &Node, ll key)
 {
       int low = 0;
       int high = Node.vec.size() - 1;
       int res = -1;
       while (low <= high)
            {
                  int mid = (low + high) >> 1;
                  if (Node.vec[mid].val == key)
                  {
                        res = Node.vec[mid].id;
                        high = mid - 1;
                  }
                  else if (Node.vec[mid].val < key)
                  {
                        low = mid + 1;
                  }
                  else
                  {
                        high = mid - 1;
                  }
            }
            return {res, max(0, low)};  // res : actual index, low : upper_bound
      }
      information getDisIndex(MergeSortTree &Node, ll key)
      {
            information p = BinarySearch(Node, key);
            int res = p.val;
            int low = p.id;
            if (p.val != -1)
            {
                  return {0, p.val};
            }
            else
            {
                  ll diff1 = 1e16;
                  ll diff2 = 1e16;
                  ll diff3 = 1e16;
                  int len = Node.vec.size();
                  if (low < len)
                  {
                        diff1 = abs(key - Node.vec[low].val);
                  }
                  if (low - 1 >= 0)
                  {
                        diff2 = abs(key - Node.vec[low - 1].val);
                  }
                  if (low + 1 < len)
                  {
                        diff3 = abs(key - Node.vec[low + 1].val);
                  }
                  ll minDif = min(diff1, min(diff2, diff3));
                  ll finalDiff = minDif;
                  int finalPos = 1e7;
                  if (minDif == diff1)
                  {
                        ll pp = BinarySearch(Node, Node.vec[low].val).val;
                        if (pp < finalPos)
                              finalPos = pp;
                  }
                  if (minDif == diff2)
                  {
                        ll pp = BinarySearch(Node, Node.vec[low-1].val).val;
                        if (pp < finalPos)
                              finalPos = pp;
                  }
                  if (minDif == diff3)
                  {
                        ll pp = BinarySearch(Node, Node.vec[low+1].val).val;
                        if (pp < finalPos)
                              finalPos = pp;
                  }
                  return {minDif, finalPos};
            }
      }
      information MergeInQuery(information &L, information &R, ll key)
      {
            if (L.id == -1)
            {
                  return R;
            }
            else if (R.id == -1)
            {
                  return L;
            }
            else
            {
                  if (L.val == R.val)
                  {
                        return {L.val, min(L.id, R.id)};
                  }
                  else if (L.val < R.val)
                  {
                        return L;
                  }
                  else
                  {
                        return R;
                  }
            }
      }
} TREE[MAXN * 4];
 
ll arr[MAXN];
 
void build(int node, int a, int b)
{
      if (a > b) return;
      if (a == b)
      {
            TREE[node].assignLeaf(arr[a], a);
            return;
      }
      int left = node << 1;
      int right = left | 1;
      int mid = (a + b) >> 1;
      build(left, a, mid);
      build(right, mid + 1, b);
      TREE[node].MERGE(TREE[left], TREE[right]);
}
 
information QUERY(int node, int a, int b, int i, int j, ll key)
{
      if (a > b or a > j or b < i) return {-1, -1};
      if (a >= i && b <= j)
      {
            MergeSortTree r;
            information p = r.getDisIndex(TREE[node], key);
            return p;
      }
      int left = node << 1;
      int right = left | 1;
      int mid = (a + b) >> 1;
      information p = QUERY(left, a, mid, i, j, key);
      information q = QUERY(right, mid + 1, b, i, j, key);
      MergeSortTree r;
      return r.MergeInQuery(p, q, key);
}
 
int main()
{
      //freopen("in.txt", "r", stdin);
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
 
      int tc;
      cin >> tc;
      for (int tcase = 1; tcase <= tc; tcase++)
      {
            int tNum;
            cin >> tNum;
            for (int i = 1; i <= tNum; i++)
            {
                  cin >> arr[i];
            }
            build(1, 1, tNum);
            int tQuery;
            cin >> tQuery;
            while (tQuery--)
            {
                  int L, R;
                  ll K;
                  cin >> L >> R >> K;
                  information ans = QUERY(1, 1, tNum, L, R, K);
                  cout << ans.id << endl;
            }
            for (int i = 0; i < MAXN*4; i++)
            {
                  TREE[i].vec.clear();
            }
      }
}