fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long solve(vector<int>& nums) {
  5.     int n = nums.size();
  6.  
  7.     // count subarrays with even odd count using prefix parity
  8.     long long cnt[2] = {1, 0}; // even, odd parity counts
  9.     int parity = 0;
  10.     long long ans = 0;
  11.  
  12.     for (int x : nums) {
  13.         parity ^= (x & 1);
  14.         ans += cnt[parity];
  15.         cnt[parity]++;
  16.     }
  17.  
  18.     // count all-odd subarrays by length parity
  19.     long long evenLen = 0, oddLen = 0;
  20.     int len = 0;
  21.  
  22.     for (int i = 0; i <= n; i++) {
  23.         if (i < n && (nums[i] & 1)) {
  24.             len++;
  25.         } else {
  26.             if (len > 0) {
  27.                 long long a = (len + 1) / 2; // odd positions
  28.                 long long b = len / 2;       // even positions
  29.                 oddLen += a * (a + 1) / 2 + b * (b + 1) / 2;
  30.                 evenLen += a * b;
  31.                 len = 0;
  32.             }
  33.         }
  34.     }
  35.  
  36.     // balanced = (even odd count AND not all-odd) OR (all-odd AND odd length)
  37.     return ans - evenLen + oddLen;
  38. }
  39.  
  40. int main() {
  41.     ios::sync_with_stdio(false);
  42.     cin.tie(nullptr);
  43.  
  44.     int n;
  45.     cin >> n;
  46.  
  47.     vector<int> nums(n);
  48.     for (int i = 0; i < n; i++) {
  49.         cin >> nums[i];
  50.     }
  51.  
  52.     cout << solve(nums) << "\n";
  53.     return 0;
  54. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
243024081
https://ideone.com/8mBc5f
language:
C++14 (gcc 8.3)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!