# HackerEarth Sub-array functions problem solution

In this HackerEarth Sub-array functions problem solution You are given an array A containing N integers. The following functions are defined for this array:
1. f1(l,r) = XOR of the first M smallest elements in the subarray from l to r, l <= rand
2. f2(l,r) = XOR of the first P largest elements in the subarray from l to r, l <= r and r - l + 1 >= P
3. f3(l,r) = f1(l,r) & f2(l,r), l <= r
Write a program to find l and r such that f3(l,r) is maximum. If there are several values of l and r for which f3(l,r) is maximum, return the one having the largest length. If multiple values still exist, return the one with the smallest l.

## HackerEarth Sub-array functions problem solution.

`#include <bits/stdc++.h>#define ll long longusing namespace std;int main(){    int t;    cin >> t;    assert(1 <= t && t <= 5);    for (int tt = 1; tt <= t; tt++) {        int n, m, p;        cin >> n >> m >> p;        assert(1 <= m && m <= 10);        assert(1 <= p && p <= 10);        assert(max(m, p) <= n && n <= 2000);        vector <ll> a(n + 1);        for (int i = 1; i <= n; i++) {            cin >> a[i];            assert(0 <= a[i] && a[i] <= 1e9);        }        int l, r;        ll ans = INT_MIN;        l = r = -1;        for (int i = 1; i <= n; i++) {            priority_queue <ll> pq_max;            priority_queue <ll> pq_min;            pq_min.push(-a[i]);            pq_max.push(a[i]);            int xx = min(p, m) - 1;            if (i + xx > n) break;            ll res1 = a[i];            ll res2 = a[i];            ll temp = INT_MIN;            int x = -1;            for (int j = i + 1; j <= n; j++) {                if (pq_max.size() < m) {                    pq_max.push(a[j]);                    res1 ^= a[j];                } else {                    ll curr_max = pq_max.top();                    if (curr_max > a[j]) {                        pq_max.pop();                        pq_max.push(a[j]);                        res1 ^= curr_max;                        res1 ^= a[j];                    }                }                if (pq_min.size() < p) {                    pq_min.push(-a[j]);                    res2 ^= a[j];                } else {                    ll curr_min = -(pq_min.top());                    if (curr_min < a[j]) {                        pq_min.pop();                        pq_min.push(-a[j]);                        res2 ^= curr_min;                        res2 ^= a[j];                    }                }                if (pq_max.size() == m && pq_min.size() == p) {                    ll curr = res1&res2;                    if (temp <= curr) {                        temp = curr;                        x = j;                    }                }            }            if (ans < temp) {                l = i;                r = x;                ans = temp;            } else if (ans == temp && (r-l) < (x - i)) {                l = i;                r = x;                ans = temp;            }        }        assert(1 <= l && l <= n);        assert(r - l + 1 >= max(p, m) && r >= 1 && r <= n);        cout << l << " " << r <<" " << ans << endl;    }    return 0;}`

### Second solution

`#include<bits/stdc++.h>using namespace std;#define FOR(i,a,b) for(i= a ; i < b ; ++i)#define rep(i,n) FOR(i,0,n)#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define si(n) scanf("%d",&n)#define pin(n) printf("%d\n",n)#define MAX 1000006#define inf (int)(1e9)int n,m,p,amin,amax,arr[MAX];multiset<int> smin,smax;bool inline justice(){    int s1,s2;    s1 = smin.size(); s2 = smax.size();    if(s1==m && s2==p)        return true;     return false;}void inline insertminimum(int num){    int sz;    sz = smin.size();    if(sz<m)    {        smin.insert(num);        amin^=num;    }    else    {        int val = *smin.rbegin();        if(num<val)        {            smin.erase(smin.find(val));            smin.insert(num);            amin^=val;            amin^=num;        }    }}void inline insertmaximum(int num){    int sz;    sz = smax.size();    if(sz<p)    {        smax.insert(num);        amax^=num;    }    else    {        int val = *smax.begin();        if(num>val)        {            smax.erase(smax.find(val));            smax.insert(num);            amax^=val;            amax^=num;        }    }}int main(){    int t;    si(t);    assert(t>=1 && t<=5);    while(t--)    {        si(n); si(m); si(p);        assert(m>=1 && m<=10);        assert(p>=1 && p<=10);        assert(n>=max(p,m) && n<=2000);        int i,j,ans,al,ar,calc,sz;        rep(i,n)        {            si(arr[i]);            assert(arr[i]>=0 && arr[i]<=inf);        }        ans = -1;        al=-1; ar=-1;        rep(i,n)        {            smin.clear(); smax.clear();            amin=amax=0;            FOR(j,i,n)            {                insertminimum(arr[j]);                insertmaximum(arr[j]);                if(justice())                {                    calc = amin & amax;                    /*if(i==2)                        trace5(i,j,amin,amax,calc);*/                    if(calc>ans)                    {                        ans = calc;                        al = i;                        ar = j;                    }                    else if(calc==ans)                    {                        sz = j-i+1;                        if(sz > ar-al+1)                        {                            al = i;                            ar = j;                        }                    }                }            }        }        printf("%d %d %d\n",al+1,ar+1,ans);    }    return 0;}`