[Hackerearth] Curious Queries

 

Problem Link    : Curious Queries
Category        : Merge Sort Tree
Contest         : December Circuits'23  

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
using pii = pair<int, int>;
 
const int maxn = 1e5 + 5;
 
struct MergesortTree {
    vector<pii> store;
    MergesortTree() {
        store.clear();
    }
 
    void assignLeaf(int val) {
        store.clear();
        store.push_back({val, val});
    }
    void marge(const MergesortTree &lchild, const MergesortTree &rchild) {
        int i = 0;
        int j = 0;
        store.clear();
        while (i < lchild.store.size() and j < rchild.store.size()) {
            if (lchild.store[i].first < rchild.store[j].first) {
                int sum = lchild.store[i].first + (store.size() ? store.back().second : 0);
                store.emplace_back(lchild.store[i].first, sum);
                i++;
            } else {
                int sum = rchild.store[j].first + (store.size() ? store.back().second : 0);
                store.emplace_back(rchild.store[j].first, sum);
                j++;
            }
        }
        while (i < lchild.store.size()) {
            int sum = lchild.store[i].first + (store.size() ? store.back().second : 0);
            store.emplace_back(lchild.store[i].first, sum);
            i++;
        }
        while (j < rchild.store.size()) {
            int sum = rchild.store[j].first + (store.size() ? store.back().second : 0);
            store.emplace_back(rchild.store[j].first, sum);
            j++;
        }
    }
    int getSum(int limit) {
        int id = upper_bound(store.begin(), store.end(), pii(limit, INT_MAX)) - store.begin();
        if (id == store.size()) {
            return 0;
        }
        int sum = store.back().second - (id - 1 >= 0 ? store[id - 1].second : 0);
        return sum;
    }
} Tree[maxn * 4];
 
int n;
int q;
int arr[maxn];
 
void build(int node, int a, int b) {
    if (a == b) {
        Tree[node].assignLeaf(arr[a]);
        return;
    }
    int lchild = node * 2;
    int rchild = node * 2 + 1;
    int mid = (a + b) / 2;
    build(lchild, a, mid);
    build(rchild, mid + 1, b);
    Tree[node].marge(Tree[lchild], Tree[rchild]);
}
 
int query(int node, int a, int b, int i, int j, int limit) {
    if (a > b or a > j or b < i) {
        return 0;
    }
    if (a >= i and b <= j) {
        return Tree[node].getSum(limit);
    }
    int lchild = node * 2;
    int rchild = node * 2 + 1;
    int mid = (a + b) / 2;
    int p = query(lchild, a, mid, i, j, limit);
    int q = query(rchild, mid + 1, b, i, j, limit);
    return p + q;
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = 1;
    if (FILEIO and fopen("in.txt", "r")) {
        freopen("F2.txt", "r", stdin);
    }
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++) {
        cin >> n >> q;
        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
        }
        build(1, 1, n);
        for (int i = 1; i <= q; i++) {
            int l, r;
            cin >> l >> r;
            l++;
            r++;
            int limit = arr[r];
            int ans = query(1, 1, n, 1, l, limit);
            cout << ans << " \n"[i == q];
        }
    }
}

[Devskill] DCP-523: Everything equal 2

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : DCP-523: Everything equal 2
Source            : DevSkill
Category          : Data Structure
Algorithm         : Merge Sort Tree
Verdict           : Time Limit Exceeded

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll           long long int  
#define inf          1e18  
  
static const int maxn = 5e4 + 5;  
  
struct MergeSortTree  
{  
      #define vll           vector <ll>  
      #define eb            emplace_back  
      #define sz(v)         (int)v.size()  
  
      vll v;  
      vll stree;  
  
      inline void assignLeaf(ll val)  
      {  
            v.eb(val);  
      }  
      inline void marge(const MergeSortTree &lft, const MergeSortTree &rgt)  
      {  
            int lenLeft = sz(lft.v);  
            int lenRight = sz(rgt.v);  
            int idLeft = 0;  
            int idRight = 0;  
            while (idLeft < lenLeft && idRight < lenRight)  
            {  
                  ll numLeft = lft.v[idLeft];  
                  ll numRight = rgt.v[idRight];  
                  if (numLeft < numRight)  
                  {  
                        v.eb(numLeft);  
                        ++idLeft;  
                  }  
                  else  
                  {  
                        v.eb(numRight);  
                        ++idRight;  
                  }  
            }  
            while (idLeft < lenLeft)  
            {  
                  v.eb(lft.v[idLeft]);  
                  ++idLeft;  
            }  
            while (idRight < lenRight)  
            {  
                  v.eb(rgt.v[idRight]);  
                  ++idRight;  
            }  
      }  
      inline void reSize()  
      {  
            int len = sz(v);  
            stree.resize(len+1);  
      }  
      inline void build()  
      {  
            int len = sz(v);  
            stree[0] = v[0];  
            for (int i = 1; i < len; i++) stree[i] = stree[i-1] + v[i];  
      }  
      inline ll getSum(int i, int j)  
      {  
            if (i > j) return 0;  
            ll sum = stree[j];  
            if (i > 0) sum -= stree[i-1];  
            return sum;  
      }  
      inline int getPos(ll val) // return last index of value  
      {  
            int lo = 0;  
            int hi = sz(v)-1;  
            int ans = -1;  
            while (lo <= hi)  
            {  
                  int mid = lo + (hi - lo) / 2;  
                  //cerr << mid << " " << v[mid] << " " << val << endl;  
                  if (v[mid] <= val)  
                  {  
                        ans = mid;  
                        lo = mid + 1;  
                  }  
                  else  
                  {  
                        hi = mid - 1;  
                  }  
            }  
            return ans;  
      }  
      inline ll sum(ll val)  
      {  
            int len = sz(v);  
            if (len == 1)  
            {  
                  return abs(val - v[0]);  
            }  
            int pos = getPos(val);  
            if (pos < 0) return inf;  
            ll presum = getSum(0, pos);  
            ll aftsum = getSum(pos+1, len-1);  
            ll need = (aftsum - (len-1-pos) * val);  
            need += ((pos+1) * val - presum);  
            return need;  
      }  
} Tree[maxn << 2];  
  
ll arr[maxn];  
int n, q;  
  
inline void build(int node, int a, int b)  
{  
      if (a == b)  
      {  
            Tree[node].assignLeaf(arr[a]);  
            return;  
      }  
      int lft = node << 1;  
      int rgt = lft | 1;  
      int mid = (a + b) >> 1;  
      build(lft, a, mid);  
      build(rgt, mid+1, b);  
      Tree[node].marge(Tree[lft], Tree[rgt]);  
      Tree[node].reSize();  
      Tree[node].build();  
}  
  
inline ll query(int node, int a, int b, int i, int j, ll val)  
{  
      if (a == i && b == j)  
      {  
            //cerr << a << " " << b << " " << i << " " << j << endl;  
            return Tree[node].sum(val);  
      }  
      int lft = node << 1;  
      int rgt = lft | 1;  
      int mid = (a + b) >> 1;  
      ll res = 0;  
      if (j <= mid)  
      {  
            res += query(lft, a, mid, i, j, val);  
      }  
      else if (i > mid)  
      {  
            res += query(rgt, mid+1, b, i, j, val);  
      }  
      else  
      {  
            res += query(lft, a, mid, i, mid, val);  
            res += query(rgt, mid+1, b, mid+1, j, val);  
      }  
      return res;  
}  
  
inline ll TernarySearch(int l, int r)  
{  
      ll lo = 1;  
      ll hi = 1e9;  
      ll mini = hi;  
      ll ans = hi;  
      while (1)  
      {  
            if (hi - lo <= 2)  
            {  
                  ll need = query(1, 1, n, l, r, lo);  
                  if (need < mini) mini = need, ans = lo;  
                  need = query(1, 1, n, l, r, lo+1);  
                  if (need < mini) mini = need, ans = lo + 1;  
                  need = query(1, 1, n, l, r, hi);  
                  if (need < mini) mini = need, ans = hi;  
                  break;  
            }  
            ll mid1 = lo + (hi - lo) / 3;  
            ll mid2 = hi - (hi - lo) / 3;  
            ll needMid1 = query(1, 1, n, l, r, mid1);  
            ll needMid2 = query(1, 1, n, l, r, mid2);  
            if (needMid1 < needMid2)  
            {  
                  if (needMid1 < mini) mini = needMid1, ans = mid1;  
                  hi = mid2;  
            }  
            else  
            {  
                  if (needMid2 < mini) mini = needMid2, ans = mid2;  
                  lo = mid1;  
            }  
      }  
      //cerr << "ans " << ans << endl;  
      return mini;  
}  
  
int main()  
{  
      //freopen("in.txt", "r", stdin);  
  
      int tc;  
      scanf("%d", &tc);  
      for (int tcase = 1; tcase <= tc; tcase++)  
      {  
            scanf("%d %d", &n, &q);  
            for (int i = 1; i <= n; i++) scanf("%d", arr+i);  
            build(1, 1, n);  
            while (q--)  
            {  
                  int l, r;  
                  scanf("%d %d", &l, &r);  
                  if (l == r)  
                  {  
                        puts("0");  
                        continue;  
                  }  
                  ll need = TernarySearch(l, r);  
                  printf("%lld\n", need);  
            }  
            for (int i = 0; i < (maxn << 2); i++)  
            {  
                  Tree[i].v.clear();  
                  Tree[i].stree.clear();  
            }  
      }  
}