Устойчивость стены~--- это число горизонтальных кирпичей минус число вертикальных. Так как горизонтальный кирпич длины хотя бы $$$2$$$, в одном ряду можно разместить не более $$$\lfloor\frac{m}{2}\rfloor$$$ горизонтальных кирпичей. Поэтому ответ не превосходит $$$n \cdot \lfloor\frac{m}{2}\rfloor$$$. С другой стороны, если размещать в ряду горизонтальные кирпичи длины $$$2$$$, и, когда $$$m$$$ нечётно, последний кирпич длины $$$3$$$, то в каждом ряду будет ровно $$$\lfloor\frac{m}{2}\rfloor$$$ горизонтальных кирпичей, и вертикальных кирпичей в стене вообще не будет. Так достигается максимальная устойчивость $$$n \cdot \lfloor\frac{m}{2}\rfloor$$$. Решение~--- это одна формула, асимптотика $$$O(1)$$$.

#include <bits/stdc++.h>

using namespace std;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        int64_t n,m;
        cin >> n >> m;
        cout << n*(m/2) << '\n';
    }
    return 0;
}

Заметим, что операциями вида: поменять местами $$$a_i$$$ с $$$a_j$$$ и $$$b_i$$$ с $$$b_j$$$ одновременно можно переставить массив $$$a$$$ как угодно, но одному и тому же $$$a_i$$$ будет соответствовать одно и то же $$$b_i$$$(потому что меняем и $$$a_i$$$ и $$$b_i$$$ сразу). Давайте отсортируем такими операциями массив $$$a$$$. Тогда суммой количества инверсий в $$$a$$$ и $$$b$$$ будет количество инверсий в $$$b$$$, так как $$$a$$$ отсортирован. Утверждается, что это минимальная сумма, которую можно достичь.

Доказательство: Рассмотрим две пары элементов $$$a_i$$$ с $$$a_j$$$ и $$$b_i$$$ с $$$b_j$$$ ($$$i$$$ < $$$j$$$). В каждой из этих пар может быть либо $$$0$$$, либо $$$1$$$ инверсия, то есть среди двух пар либо $$$0$$$, либо $$$1$$$, либо $$$2$$$ инверсии. Если до операции было $$$0$$$ инверсий, то после операции станет две, если была $$$1$$$, то и останется $$$1$$$, если было $$$2$$$ то станет $$$0$$$. Если перестановка $$$a_i$$$ отсортирована то в каждой паре индексов $$$i$$$ и $$$j$$$ будет максимум $$$1$$$ инверсия, поэтому любая пара индексов будет давать не больше инверсий, чем если их поменять. Поскольку в каждой паре количество инверсий минимально возможное, то и общее количество инверсий минимально возможное.

Асимптотика: $$$O(n)$$$ на набор входных данных.

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        pair<int,int> ab[n];
        for(int i = 0;i < n;++i)
        {
            cin >> ab[i].first;
        }
        for(int i = 0;i < n;++i)
        {
            cin >> ab[i].second;
        }
        sort(ab,ab+n);
        for(int i = 0;i < n;++i)
        {
            cout << ab[i].first << ' ';
        }
        cout << "\n";
        for(int i = 0;i < n;++i)
        {
            cout << ab[i].second << ' ';
        }
        cout << "\n";
    }
}

Рассмотрим битовое представление чисел $$$a$$$, $$$b$$$, $$$x$$$. Посмотрим на какие-то $$$2$$$ бита на одинаковой позиции в $$$a$$$ и $$$b$$$, если они одинаковы, то независимо от того что стоит в $$$x$$$, в числе $$$|({a \oplus x}) - ({b \oplus x})|$$$ на той же позиции будет стоять $$$0$$$. Поэтому на все такие позиции в $$$x$$$ выгодно поставить 0 (так как мы хотим чтобы выполнялось $$$x \leq r$$$, а от бита ответ все равно не зависит). Если же биты в $$$a$$$ и $$$b$$$ на одной позиции отличаются, то на этой позиции будет $$$1$$$ либо в $$$a \oplus x$$$, либо в $$$b \oplus x$$$ в зависимости от того что стоит на этой позиции в $$$x$$$.

Пусть $$$a$$$ < $$$b$$$, если нет то поменяем их местами. Тогда на старшей позиции, из тех где биты различаются, в $$$a$$$ стоит $$$0$$$, а в $$$b$$$ стоит $$$1$$$. Есть $$$2$$$ варианта, либо поставить на эту позицию $$$1$$$ в $$$x$$$ (и тогда будет $$$1$$$ в $$$a \oplus x$$$), либо поставить $$$0$$$ в $$$x$$$ (и тогда будет $$$0$$$ в $$$a \oplus x$$$).

Пусть мы поставили $$$0$$$ в $$$x$$$, тогда $$$a \oplus x$$$ точно будет меньше чем $$$b \oplus x$$$ (потому что в старшем различающемся бите $$$a \oplus x$$$ имеет $$$0$$$, а $$$b \oplus x$$$ имеет $$$1$$$). Поэтому на всех следующих позициях выгодно делать $$$1$$$ в $$$a \oplus x$$$, ведь так мы максимально приблизим эти числа, сделаем меньше их разность. Поэтому можно пойти по убыванию позиций, и если позиция различающаяся, то сделаем на этой позиции $$$1$$$ в $$$a \oplus x$$$ если это возможно (если при этом $$$x$$$ не превысит $$$r$$$).

Второй случай(когда мы поставили $$$1$$$ в $$$x$$$ на позицию первого различающегося бита) разбирается аналогично, но на самом деле он не нужен, ведь в нем ответ не станет меньше, а $$$x$$$ станет больше.

Асимптотика: $$$O(\log 10^{18})$$$ на набор входных данных.

#include <bits/stdc++.h>

using namespace std;

const int maxb = 60;

bool get_bit(int64_t a,int i)
{
    return a&(1ll<<i);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        int64_t a,b,r;
        cin >> a >> b >> r;
        int64_t x = 0;
        bool first_bit = 1;
        if(a > b)
            swap(a,b);
        for(int i = maxb-1;i >= 0;--i)
        {
            bool bit_a = get_bit(a,i);
            bool bit_b = get_bit(b,i);
            if(bit_a != bit_b)
            {
                if(first_bit)
                {
                    first_bit = 0;
                }
                else
                {
                    if(!bit_a && x+(1ll<<i) <= r)
                    {
                        x += (1ll<<i);
                        a ^= (1ll<<i);
                        b ^= (1ll<<i);
                    }
                }
            }
        }
        cout << b-a << "\n";
    }
}