AcWing 1945. Cow Baseball (1 2 points 2 double pointers)

Let’s start with the simplest way to think about the triple loop. We can try to eliminate the innermost loop and only enumerate x and y.

#include 

using namespace std;
int q[1010];

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> q[i];
    sort(q + 1, q + n + 1);

    int res = 0;
    // for(int i = 1; i <= n; i ++)
    // {
    //     for(int j = i + 1; j <= n; j ++)
    //     {
    //         int l = lower_bound(q + 1, q + n + 1, 2 * q[j] - q[i]) - q;
    //         int r = upper_bound(q + 1, q + n + 1, 3 * q[j] - 2 * q[i]) - q;
    //         res += r - l;
    //     }
    // }

    for(int i = 1; i + 2 <= n; i++)
        for(int j = i + 1, l = j, r = j; j + 1 <= n; j++)
        {
            while(l <= n && q[l] < 2 * q[j] - q[i])    l ++;
            while(r <= n && q[r] <= 3 * q[j] - 2 * q[i])  r ++;
            res += r - l;
        }
    cout << res << endl;
    return 0;
}