Consider the case for just 2 numbers $$$a$$$ and $$$b$$$. Let $$$x_a$$$ and $$$x_b$$$ be the msb of $$$a$$$ and $$$b$$$.

Claim: $$$a\space AND\space b > a\space XOR\space b \space \iff \space x_a = x_b$$$ and $$$a\space AND\space b \neq a\space XOR\space b \space \forall \space a, b$$$

So to calculate the answer we just need to count the number of pair of numbers with different msb. This can be done in $$$O(N)$$$

//OverRancid#0590
#include <bits/stdc++.h>    //Parental Advisory
using namespace std;       //Explicit Content

#define unsigned unsigned long long
#define double long double
void yes(){cout<<"YES\n";}
void no(){cout<<"NO\n";}
void yn(bool x){x? yes(): no();}
#define int long long

int32_t main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    uint64_t _, i;
    cin >> _;
    while (_--) {
        int n;
        cin >> n;
        unordered_map<int, int> b;
        for (i=0; i<n; i++) {
            int a;
            cin >> a;
            b[__builtin_clz(a)]++;
        }
        int answer = n * (n-1) / 2;
        for (pair<int, int> bx: b) {
            answer -= bx.second * (bx.second - 1) / 2;
        }

        cout << answer << "\n";
    }
    return 0;
}

This task can be solved using dp. Let's define our dp state as:

$$$f(i, 0) =$$$ minimum cost of reaching the $$$i^{th}$$$ red station.

$$$f(i, 1) =$$$ minimum cost of reaching $$$i^{th}$$$ blue station.

It is easy to see the transition rules:

As we start from the first red station we can initialize $$$f(1, 0) = 1$$$ and populate the dp in a top-down fashion. The final answer is the minimum from $$$f(n+1, 0)$$$ and $$$f(n+1, 1)$$$

Alternate Solution: We can also model this situation as a directed graph with separate red and blue vertices. We then run a shortest path algorithm starting from the first red vertex and the answer will be the minimum distance among the $$$(n+1)^{st}$$$ red and blue vertex. For more information on such tasks go through the following blog

Both these solutions work in $$$O(N)$$$

//Created by Mehul G.
#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin >> T;
    while (T--)
    {
        long long N, R, B;
        cin >> N >> R >> B;
        vector<long long> red(N + 1, 0);
        vector<long long> blue(N + 1, 0);
        for (int i = 1; i <= N; i++)
        {
            cin >> red[i];
        }
        for (int i = 1; i <= N; i++)
        {
            cin >> blue[i];
        }
        vector<vector<long long>> dp(N + 1, vector<long long>(2, LONG_LONG_MAX));
        dp[0][0] = 0;
        dp[0][1] = B;
        for (int i = 1; i <= N; i++)
        {
            dp[i][0] = min(dp[i - 1][0], dp[i - 1][1] + R) + red[i];
            dp[i][1] = min(dp[i - 1][0] + B, dp[i - 1][1]) + blue[i];
        }
        cout << min(dp[N][0], dp[N][1]) << endl;
    }
    return 0;
}

//OverRancid#0590
#include <bits/stdc++.h>    //Parental Advisory
using namespace std;       //Explicit Content

#define unsigned unsigned long long
#define double long double
void yes(){cout<<"YES\n";}
void no(){cout<<"NO\n";}
void yn(bool x){x? yes(): no();}
#define int long long

static const int N = 2e5+3;
vector<vector<pair<int, int>>> adj(N);
vector<int> d;

void dijkstra(int s){
    d[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({0, s});
    while(!q.empty()){
        int v = q.top().second;
        int d_v = q.top().first;
        q.pop();

        if(d_v != d[v]){
            continue;
        }

        for(pair<int, int> edge: adj[v]){
            int u = edge.first;
            int w = edge.second;

            if(d[v] + w < d[u]){
                d[u] = d[v] + w;
                q.push({d[u], u});
            }
        }
    }
}

int32_t main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    uint64_t _, i;
    cin >> _;
    while (_--) {
        int n, r, b, a;
        cin >> n >> r >> b;

        for (i=1; i<=n+1; i++) {
            adj[i].clear();
            adj[i + n+1].clear();
        }
        for (i=1; i<=n; i++) {
            cin >> a;
            adj[i].push_back({i+1, a});
            adj[i].push_back({i+(n+1), b});
        }
        for (i=1; i<=n; i++) {
            cin >> a;
            adj[i + (n+1)].push_back({i+1 + (n+1), a});
            adj[i + (n+1)].push_back({i, r});
        }
        adj[n+1].push_back({2*(n+1), b});
        adj[2*(n+1)].push_back({n+1, r});

        d = vector<int>(2*n+5, 5e15);
        dijkstra(1);

        cout << min(d[n+1], d[2*n+2]) << "\n";
    }
    return 0;
}

This task can be solved using the sliding window like technique. In each window we maintain 3 things to ensure we don't exceed our limit on number of operations.

• multiset $$$useX$$$: consisting of all numbers on which we wish to apply operation of type 1.
• multiset $$$useY$$$: consisting of all numbers on which we wish to apply operation of type 2.
• integer $$$sumX$$$: the sum of all numbers on which we wish to apply operation of type 1.

A window (subarray) can be considered valid if:

• size of $$$useY \le Y$$$
• $$$sumX \le X$$$

For any window we can greedily keep applying as many operations of type 2 as possible. Once this is no longer possible we apply operation of type 1 on the smallest numbers in the window.

This can be implemented in $$$O(N\log N)$$$ using std::multiset or ordered set from __gnu_pbds.

//OverRancid#0590
#include <bits/stdc++.h>    //Parental Advisory
using namespace std;       //Explicit Content

#define unsigned unsigned long long
#define double long double
void yes(){cout<<"YES\n";}
void no(){cout<<"NO\n";}
void yn(bool x){x? yes(): no();}
#define int long long

int32_t main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, x, y, i, j;
    cin >> n >> x >> y;
    vector<int> a(n);
    for (i=0; i<n; i++) {
        cin >> a[i];
    }

    multiset<int> useX, useY;
    int answer = 0, sumX = 0;
    for (i=0, j=0; i<n; i++) {
        useY.insert(a[i]);

        while (useY.size() > y) {
            int small = *useY.begin();
            sumX += small;
            useX.insert(small);
            useY.erase(useY.begin());
        }

        while (sumX > x) {
            int last = a[j];
            if (useX.count(a[j])) {
                sumX -= a[j];
                useX.erase(useX.find(a[j])); 
            }
            else {
                useY.erase(useY.find(a[j]));
                int big = *useX.rbegin();
                sumX -= big;
                useX.erase(useX.find(big));
                useY.insert(big);
            }
            j++;
        }

        answer = max(answer, (useX.size() + useY.size()) * 1LL);
    }
    cout << answer << "\n";

    return 0;
}

// Created by Mehul G.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ordered_set tree<pair<int, int>, null_type, greater<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long N, X, Y, x_used, ans;
    cin >> N >> X >> Y;
    ordered_set o_set;
    vector<long long> store(N);
    for (int i = 0; i < N; i++)
    {
        cin >> store[i];
    }
    x_used = ans = 0;
    long long i = 0;
    for (int j = 0; j < N; j++)
    {
        if (o_set.size() >= Y)
        {
            o_set.insert({store[j], j});
            int ind = o_set.order_of_key({store[j], j});
            if(ind >= Y){
                x_used += store[j];
            }
            else{
                auto itr = *o_set.find_by_order(Y);
                x_used += itr.first;
            }
            while (x_used > X)
            {
                ind = o_set.order_of_key({store[i], i});
                if (ind >= Y)
                {
                    x_used -= store[i];
                }
                else
                {
                    auto itr = *o_set.find_by_order(Y);
                    x_used -= itr.first;
                }
                o_set.erase({store[i], i});
                i++;
            }
            ans = max(ans, j - i + 1);
        }
        else
        {
            o_set.insert({store[j], j});
            ans = max(ans, j - i + 1);
        }
    }
    cout << ans << endl;
    return 0;
}