give solution in cpp C. Coloring Game time limit ...

cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        // Ensure the array is sorted (though input guarantees non-decreasing order)
        sort(a.begin(), a.end());

        ll ans = 0;
        // For each k as the index of the third red element (0-based)
        for (int k = 2; k < n; k++) {
            // T = max(a[k], a[n-1] - a[k])
            int T = max(a[k], a[n-1] - a[k]);
            // Count pairs (i, j) with 0 <= i < j < k and a[i] + a[j] > T
            int l = 0, r = k - 1;
            while (l < r) {
                if (a[l] + a[r] > T) {
                    // All pairs (l, l+1), (l, l+2), ..., (l, r-1) with r fixed
                    ans += (r - l);
                    r--;
                } else {
                    l++;
                }
            }
        }

        cout << ans << "\n";
    }

    return 0;
}

Explanation of the approach:

1. Reformulating the win conditions
   Alice picks three indices $i<j<k$. Let $S = a_i + a_j + a_k$.

   • If Bob picks one of Alice's chosen indices (say $k$), he removes that red element and colors it blue, leaving red sum $S - a_k$. Alice needs $$S - a_k > a_k \quad\Longleftrightarrow\quad S > 2\,a_k.$$
   • If Bob picks an element outside Alice's triple, say at index $m$, the red sum remains $S$, and Alice needs $$S > a_m.$$ Bob will choose the largest outside element, which is $a_{n-1}$ if $k = n-1$ or $a_{n}$ otherwise.

   Combining both, the necessary and sufficient condition for the triple $(i,j,k)$ to be safe is

   $$S > \max\!\bigl(2\,a_k,\;\max_{m \not\in\{i,j,k\}} a_m\bigr).$$

   One can show this reduces to

   $$a_i + a_j > \max\bigl(a_k,\;a_{n-1} - a_k\bigr) \quad (\text{using 0-based indexing with }n-1\text{ as the last index}).$$

2. Two-pointer counting

   • For each choice of the largest red index $k$ (from 2 to $n-1$ in 0-based), compute
     $\displaystyle T = \max\bigl(a[k],\,a[n-1] - a[k]\bigr).$
   • Count the number of pairs $(i,j)$ with $0 \le i < j < k$ such that $a[i] + a[j] > T$.
   • This is done in $O(k)$ time per $k$ using the classic two-pointer technique on the sorted prefix $a[0 \dots k-1]$.

3. Complexity

   • Sorting each test is $O(n\log n)$ (though input is already sorted).
   • The double loop with two-pointers is $O(n^2)$.
   • Since the sum of $n$ across all test cases is at most 5000, the overall time remains well within the 2.5 s limit.

This yields a total runtime of roughly $O\bigl(\sum n^2\bigr)\le 25\times 10^6$ operations, which is efficient enough under the given constraints.