HackerEarth Large Sub-Arrays problem solution

In this HackerEarth Large Sub-Arrays problem solution You are given an array A with size N and two integers M and K.

Let's define another array B with size N x M as the array that's formed by concatenating M copies of array A.

You have to find the number of sub-arrays of the array B with sum <= K. Since the answer can be very large you have to print the answer mod 10^9+7.

HackerEarth Large Sub-Arrays problem solution.

#include <bits/stdc++.h>
#include <tr1/unordered_map>
using namespace std;
using namespace std::tr1;
#define opt ios_base::sync_with_stdio(0)
#define lli long long int
#define ulli unsigned long long int
#define I int
#define S string
#define D double
#define rep(i,a,b) for(i=a;i<b;i++)
#define repr(i,a,b) for(i=a;i>b;i--)
#define in(n) scanf("%lld",&n)
#define in2(a,b) scanf("%lld %lld",&a,&b)
#define in3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define out(n) printf("%lld\n",n)
#define inu(a) scanf("%lld",&a)
#define outu(a) printf("%llu",a)
#define ins(s) scanf("%s",&s)
#define outs(s) printf("%s",s)
#define mod 1000000007
#define inf 100000000000000
typedef long long       ll;
typedef pair<lli,lli>  plli;
typedef vector<lli>     vlli;
typedef vector<ulli>    vulli;
typedef vector<ll>      vll;
typedef vector<string>  vs;
typedef vector<plli>     vplli;
#define MM(a,x)  memset(a,x,sizeof(a));
#define ALL(x)   (x).begin(), (x).end()
#define P(x)       cerr<<"{"#x<<" = "<<(x)<<"}"<<endl;
#define P2(x,y)       cerr<<"{"#x" = "<<(x)<<", "#y" = "<<(y)<<"}"<<endl;
#define P3(x,y,z)  cerr<<"{"#x" = "<<(x)<<", "#y" = "<<(y)<<", "#z" = "<<(z)<<"}"<<endl;
#define P4(x,y,z,w)cerr<<"{"#x" = "<<(x)<<", "#y" = "<<(y)<<", "#z" = "<<(z)<<", "#w" = "<<(w)<<"}"<<endl;
#define PP(x,i)     cerr<<"{"#x"["<<i<<"] = "<<x[i]<<"}"<<endl;
#define TM(a,b)     cerr<<"{"#a" -> "#b": "<<1000*(b-a)/CLOCKS_PER_SEC<<"ms}\n";
#define UN(v)    sort(ALL(v)), v.resize(unique(ALL(v))-v.begin())
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define sz() size()
#define nl cout<<"\n"
#define MX1 100005
#define MX2 1000005
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
lli dx[]={0,0,-1,1,-1,-1,1,1};
lli dy[]={1,-1,0,0,1,-1,-1,1};
lli power(lli a,lli b)
    {
    lli value;
    if(b==0)
        {
        return 1;
    }
    else if(b%2==0)
        {
        value=power(a,b/2)%mod;
        return(value*value)%mod;
    }
    else
        {
        value=power(a,b/2)%mod;
        return ((a*value)%mod*(value))%mod;
    }
}
string f(lli n) {
    vlli v;
    lli i;
    if(n==0) {
        return "00";
    }
    string s="0";
    while(n) {
        v.pb(n%10);
        n/=10;
    }
    reverse(ALL(v));
    rep(i,0,v.sz()) {
        s+=(v[i]+'0');
    }
    return s;
}
lli a[100005],pref[100005],suf[100005];
int main()
{
    /*lli files=10;
    while(files--) {
    #ifndef ONLINE_JUDGE
        string input="in"+f(files)+".txt";
        string output="out"+f(files)+".txt";
        freopen(input.c_str(),"r",stdin);
        freopen(output.c_str(),"w",stdout);
        #endif*/
        opt;
        lli t;
        cin>>t;
        while(t--) {
            lli n,m,k;
            cin>>n>>m>>k;
            lli ans=0,i,sum=0;
            rep(i,1,1+n) {
                cin>>a[i];
                pref[i]=a[i];
                suf[i]=a[i];
                sum+=a[i];
            }
            sum*=m;
            if(sum<=k) {
                lli temp=(n*m)%mod;
                ans=(temp*(temp+1))%mod;
                ans=(ans*power(2,mod-2))%mod;
                cout<<ans<<endl;
                continue;
            }
            sum/=m;
            rep(i,2,1+n) {
                pref[i]+=pref[i-1];
            }
            repr(i,n-1,0) {
                suf[i]+=suf[i+1];
            }
            rep(i,1,1+n) {
                if(suf[i]>=k) {
                    lli temp=-1,l=i,r=n;
                    while(l<=r) {
                        lli mid=(l+r)/2;
                        if((pref[mid]-pref[i-1])<=k) {
                            temp=mid;
                            l=mid+1;
                        } else {
                            r=mid-1;
                        }
                    }
                    if(temp!=-1) {
                        ans=(ans+(m*(temp-i+1)))%mod;
                    }
                    continue;
                }
                if((suf[i]+(m-1)*sum)<=k) {
                    lli temp=(m*(2*(n-i+1)+(m-1)*n));
                    temp/=2;
                    ans=(ans+temp)%mod;
                    continue;
                }
                lli cnt=(k-suf[i])/sum;
                cnt++;
                lli temp=(cnt*(2*(n-i+1)+(cnt-1)*n));
                temp/=2;
                temp%=mod;
                ans=(ans+temp)%mod;
                cnt--;
                lli val=(k-suf[i]-cnt*sum);
                lli l=1,r=n,idx=0;
                while(l<=r) {
                    lli mid=(l+r)/2;
                    if(pref[mid]<=val) {
                        idx=mid;
                        l=mid+1;
                    } else {
                        r=mid-1;
                    }
                }
                lli no=(n-i+1)+(cnt*n)+idx;
                no%=mod;
                ans=(ans+(no*(m-cnt-1)))%mod;
            }
            cout<<ans<<endl;
        }
}