[UVa] 12697 – Minimal Subarray Length

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 12697 – Minimal Subarray Length
Source            : UVa Online Judge
Category          : Data Structure
Algorithm         : Merge Sort Tree
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll              long long
#define vi              vector 
#define vl              vector 
#define eb              emplace_back
#define sz(a)           a.size()
#define pii             pair <int, int>
#define pli             pair <ll, int>
#define inf             10000000
 
static const int maxn = 2e5 + 5;
 
int N;
ll X, arr[maxn], cumsum[maxn];
 
struct info
{
    ll sum;
    int pos;
    info(ll sum = 0, int pos = 0) : sum(sum), pos(pos) {}
    friend bool operator < (info A, info B)
    {
        return A.sum < B.sum;
    }
};
 
struct mergeSortTree
{
    #define vif          vector 
    vif v;
    vi stree;  // segment tree on v
    void assignLeaf(int pos, ll val)
    {
        v.eb(val, pos);
    }
    void marge(const mergeSortTree &left, const mergeSortTree &right)
    {
        int len_left = sz(left.v);
        int len_right = sz(right.v);
        int id_left = 0, id_right = 0;
        while (id_left < len_left && id_right < len_right)
        {
            ll num_left = left.v[id_left].sum;
            ll num_right = right.v[id_right].sum;
            if (num_left < num_right)
            {
                v.eb(left.v[id_left]);
                id_left++;
            }
            else
            {
                v.eb(right.v[id_right]);
                id_right++;
            }
        }
        while (id_left < len_left)
        {
            v.eb(left.v[ id_left ]);
            id_left++;
        }
        while (id_right < len_right)
        {
            v.eb(right.v[ id_right ]);
            id_right++;
        }
    }
    void reSize()
    {
        int len = sz(v);
        stree.resize(4*len);
    }
    void build(int node, int a, int b)
    {
        if (a > b) return;
        if (a == b)
        {
            stree[node] = v[a].pos;
            return;
        }
        int lft = node << 1;
        int rgt = lft | 1;
        int mid = (a + b) >> 1;
        build(lft, a, mid);
        build(rgt, mid+1, b);
        stree[node] = min(stree[lft], stree[rgt]);
    }
    int getMin(int node, int a, int b, int i, int j)
    {
        if (a > b || a > j || b < i) return inf;
        if (a >= i && b <= j) return stree[node];
        int lft = node << 1;
        int rgt = lft | 1;
        int mid = (a + b) >> 1;
        int p1 = getMin(lft, a, mid, i, j);
        int p2 = getMin(rgt, mid+1, b, i, j);
        return min(p1, p2); // here
    }
    int getLess(ll num)
    {
        int len = v.size();
        int idx = lower_bound(v.begin(), v.end(), num) - v.begin();
        if (idx >= len) return -1;
        return idx;
    }
    void clearAll()
    {
        v.clear();
        stree.clear();
    }
} tree[maxn << 2];
 
void build(int node, int a, int b)
{
    if (a > b) return;
    if (a == b)
    {
        tree[node].assignLeaf(a, cumsum[a]);
        tree[node].reSize();
        int sze = tree[node].v.size();
        tree[node].build(1, 0, sze-1);
        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].marge(tree[left], tree[right]);
    tree[node].reSize();
    tree[node].build(1, 0, tree[node].v.size()-1);
}
 
int query(int node, int a, int b, int i, int j, ll val)
{
    if (a > b || a > j || b < i) return inf;
    if (a >= i && b <= j)
    {
        int getID = tree[node].getLess(val);
        if (getID == -1) return inf;
        int sze = sz(tree[node].v);
        int getMinIdx = tree[node].getMin(1, 0, sze-1, getID, sze-1);
        return getMinIdx;
    }
    int left = node << 1;
    int right = left | 1;
    int mid = (a + b) >> 1;
    int p1 = query(left, a, mid, i, j, val);
    int p2 = query(right, mid+1, b, i, j, val);
    return min(p1, p2);
}
 
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++)
    {
        cin >> N >> X;
        for (int i = 1; i <= N; i++)
        {
            cin >> arr[i];
            cumsum[i] = cumsum[i-1] + arr[i];
        }
        build(1, 1, N);
        int minlen = inf;
        for (int i = 1; i <= N; i++)
        {
            ll xx = X + cumsum[i-1];
            int geti = query(1, 1, N, i, N, xx);
            if (geti == inf) continue;
            if (geti - i + 1 < minlen) minlen = geti - i + 1;
        }
        if (minlen == inf) minlen = -1;
        cout << minlen << "\n";
        for (int i = 0; i < maxn; i++) cumsum[i] = 0;
        for (int i = 0; i < 4*maxn; i++) tree[i].clearAll();
    }
}

Another Problem:  D. Petya and Array