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:

f1(l,r) = XOR of the first M smallest elements in the subarray from l to r, l <= rand
f2(l,r) = XOR of the first P largest elements in the subarray from l to r, l <= r and r – l + 1 >= P
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 long
using 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("%dn",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 %dn",al+1,ar+1,ans);
    }
    return 0;
}

coding problems