Free Contest 147 - EVENTUPLES

Code

#include <bits/stdc++.h>
#define hieuhfgr ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ull unsigned long long
#define gcd __gcd
#define pb push_back
#define fi first
#define se second
#define oo 1e9;
#define endl "\n"
#define FILENAME "a"
#define file freopen(FILENAME".INP", "r", stdin);freopen(FILENAME".OUT", "w", stdout)
using namespace std;

int main(){	
	hieuhfgr;
	int n,q;
	cin >> n>> q;
	int a[n+1];
	int cnt[3][n+1];
	memset(cnt, 0, sizeof(cnt));
	for(int i=1;i <= n;i++) {
		cin >> a[i];
		for (int j=0;j<= 1;j++) cnt[j][i] = cnt[j][i-1];
		cnt[a[i]%2][i]++;
	}
	int l,r;
	while(q--) {
		cin >> l >> r;
		ll cnt2 = cnt[0][r] - cnt[0][l-1];
		ll cnt1 = cnt[1][r] - cnt[1][l-1];
		cnt1 = cnt1 * (cnt1-1) / 2;
		ll res= 0;
		if (cnt2 >= 3) res = cnt2 * (cnt2-1) / 2 * (cnt2-2) / 3;
		res = res + cnt1 * cnt2;
		cout <<res << endl;
	}
	return 0;
}