Subarray Sums II

#include <bits/stdc++.h>
using namespace std;

// Custom hash function to prevent unordered_map from worst-case performance
struct custom_hash {
    // Splitmix64 hash function for better distribution
    size_t operator()(const long long& key) const {
        size_t res = key;
        res += 0x9e3779b97f4a7c15;
        res = (res ^ (res >> 30)) * 0xbf58476d1ce4e5b9;
        res = (res ^ (res >> 27)) * 0x94d049bb133111eb;
        res = res ^ (res >> 31);
        return res;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    long long n, x;
    cin >> n >> x; // Read the size of the array and the target sum
    
    vector<long long> a(n);
    for(auto &num : a) cin >> num; // Read the array elements
    
    // Initialize an unordered_map with the custom hash
    // The map will store prefix_sum -> frequency
    unordered_map<long long, long long, custom_hash> prefix_counts;
    prefix_counts[0] = 1; // Base case: prefix_sum of 0 occurs once
    
    long long current_sum = 0; // Initialize current prefix sum
    long long answer = 0; // Initialize the answer
    
    // Iterate through the array
    for(int i = 0; i < n; ++i){
        current_sum += a[i]; // Update the current prefix sum
        
        // Check if (current_sum - x) exists in the map
        // If it does, it means there's a subarray ending at index i with sum x
        if(prefix_counts.find(current_sum - x) != prefix_counts.end()){
            answer += prefix_counts[current_sum - x];
        }
        
        // Update the map with the current prefix sum
        prefix_counts[current_sum]++;
    }
    
    cout << answer; // Output the total number of qualifying subarrays
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED