I think that the answer for the example input should be 3. 1. a[1,1] , sum=1 .... 2. a[2,2] , sum=-2 .... 3. a[1,2] , sum=-1.... are the possible subarrays

Edit: Sorry I thought B=2.

If n<=10000 actually, you can do prefix sum then for each [l,r] check the answer. If you have a typo and n<=100000, maintain a segment tree / BIT for dynamic range queries. Now for each i , increase the frequency of sum of [1,i] in the tree by 1, and add to the answer the frequencies of the range that makes the sum of [1,i] less than b

You can maintain an ordered multiset storing the prefix sums before the i'th index dynamically. Let's say you are standing at the i'th index, so you should have all prefix sums stored till the i-1'th index to be precise.

Now, we want to calculate how many subarrays ending at the i'th index have a Sum < B . So you need to search how many previous subarray prefixes are there which you can remove. More precisely, you need to find how many subarray prefixes have a [ sum >= current_sum-b+1 ] . So you can find it from the ordered set in O(log(N)) time on an average. So overall you can do it in approximately NlogN operations which would suffice the given constraints for sure.

I haven't been able to think of a O(N) solution till now.

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;

#define int long long
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 

int32_t main(){
    int n,b;
    cin>>n>>b;
    vector<int> arr(n);
    for(auto &it : arr)cin>>it;

    pbds st;
    st.insert(0);
    int sum=0;
    int ans=0;
    for(int i=0;i<n;i++){
        sum+=arr[i];
        int reqSum=sum-b+1;
        int subarrays=st.size() - st.order_of_key(reqSum);
        ans+=subarrays;
        st.insert(sum);
    }
    cout<<ans<<endl;
}



// How Could....We Ever Just Be Friends,
// I Would.. Rather Die Than Let You Go
// Juliet To Your Romeo
// When I Heard You Say........
// I Would Never Fall In Love 
// Again Until I Found You....
// I Said I Would Never Fall 
// Unless Its You I Fall Into

Can you provide link where can I submit this task. Thanks