Subarray Sums II

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    ll x;
    cin >> n >> x;
    
    vector<ll> a(n);
    for(auto &num : a) cin >> num;

    vector<ll> prefix(n+1, 0);
    for(int i = 0; i < n; ++i){
        prefix[i+1] = prefix[i] + a[i];
    }
    
    vector<ll> all_sums = prefix;

    sort(all_sums.begin(), all_sums.end());
    all_sums.erase(unique(all_sums.begin(), all_sums.end()), all_sums.end());
    
    auto get_index = [&](ll val) -> int{
        return lower_bound(all_sums.begin(), all_sums.end(), val) - all_sums.begin();
    };

    int m = all_sums.size();
    vector<int> freq(m, 0);

    freq[get_index(0)] = 1;
    
    ll result = 0;

    for(int i = 1; i <= n; ++i){
        ll current_sum = prefix[i];
        ll required_sum = current_sum - x;

        auto it = lower_bound(all_sums.begin(), all_sums.end(), required_sum);
        if(it != all_sums.end() && *it == required_sum){
            int idx = it - all_sums.begin();
            result += freq[idx];
        }

        int idx = get_index(current_sum);
        freq[idx]++;
    }
    
    cout << result;
}

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