FIRST ATTEMPT - theta(n^3)

#include <iostream>

using namespace std;

void testcase(){
    int n; cin >> n;
    int  x[n];

    for (int i = 0; i < n; i++){
        cin >> x[i];
    }

    int even_pairs = 0;
    for (int i=0; i < n; i++){
        for(int j=0; j < n; j++){
            int sum = 0;
            for (int k=i; k <= j; k++){       // DUMB
                sum += x[k];
            }
            if (sum % 2== 0){
                even_pairs++;
            }
        }
    }
}

int main() {
    int t; cin >> t;

    for (int i = 0; i < t; i++) {
        testcase();
    }
    return 0;
}

SECOND ATTEMP - theta(n^2)

    1. calculate partial sums
    2. for every i < j check the parity of Sj - Si-1

#include <iostream>

using namespace std;

void testcase(){
    int n; cin >> n;
    int  x[n];

    for (int i = 0; i < n; i++){
        cin >> x[i];
    }

    int S[n];
    S[0] = x[0]
    for (int i=1; j <n; i++){
        S[i] = x[i] + S[i-1];
    }

    int even_pairs = 0;
    for (i=0; i<n; i++){
        for (int j=i; j<n; j++){
            int sum;
            if (i==0)
                sum = S[j];
            else
                sum = S[j] - S[i-1];

            if (sum % 2 == 0)
                even_pairs++;

        }
    }
    return even_pairs;
}

int main() {
    int t; cin >> t;

    for (int i = 0; i < t; i++) {
        testcase();
    }
    return 0;
}

THIRD ATTEMP - theta(n)

#include <iostream>

using namespace std;

void testcase(){
    int n; cin >> n;
    int  x[n];

    for (int i = 0; i < n; i++){
        cin >> x[i];
    }

    int S[n];
    S[0] = x[0]
    for (int i=1; j <n; i++){
        S[i] = x[i] + S[i-1];
    }

    int even_pairs = 0;
    int even= 0, odd = 0;

    for (int i = 0; i <n ; i++){
        if (S[i] %2==0){
            even++;
        } else {
            odd++;
        }
    }

    even_pairs += (even * (even -1)) / 2;
    even_pairs += (odd* (odd-1)) / 2;
    even_pairs += even_pairs;
    return even_pairs;
}

int main() {
    int t; cin >> t;

    for (int i = 0; i < t; i++) {
        testcase();
    }
    return 0;
}