In this HackerEarth Partitions problem solution, you are given an array a of size n and two integers l and r. You have to find the number of partitions of array a such that the sum of elements in each partition lies between  and (both inclusive). Since the answer can be large, find the answer modulo 10^9 + 7 (1000000007).


HackerEarth Partitions problem solution


HackerEarth Partitions 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;
}
}
lli a[100005],dp[100005],n,L,R,dp_brute[100005],tree[400005],prefa[100004],check=0;
void update(lli n,lli s,lli e,lli idx,lli val) {
if(s==e) {
tree[n]=val;
} else {
lli mid=(s+e)/2;
if(idx<=mid) {
update(2*n,s,mid,idx,val);
} else {
update(2*n+1,mid+1,e,idx,val);
}
tree[n]=(tree[2*n]+tree[2*n+1])%mod;;
}
}
lli query(lli n,lli s,lli e,lli l,lli r) {
if(s>e or s>r or e<l) {
return 0;
}
if(s>=l and e<=r) {
return tree[n]%mod;
}
lli mid=(s+e)/2;
return (query(2*n,s,mid,l,r)+query(2*n+1,mid+1,e,l,r))%mod;
}
int main()
{
opt;
cin>>n>>L>>R;
lli i,j,flag=0;
rep(i,1,1+n) {
cin>>a[i];
if(a[i]>R) {
flag=1;
}
prefa[i]=prefa[i-1]+a[i];
}
if(flag) {
cout<<0<<endl;
exit(0);
}
update(1,1,n+1,n+1,1);
lli sumL=0,sumR=0,add=1,l=n-1,r=n-1;
repr(i,n,0) {
lli st=-1,en=-1;
lli l=i,r=n;
while(l<=r) {
lli mid=(l+r)/2;
if((prefa[mid]-prefa[i-1])>=L) {
st=mid;
r=mid-1;
} else {
l=mid+1;
}
}
l=i,r=n;
while(l<=r) {
lli mid=(l+r)/2;
if((prefa[mid]-prefa[i-1])<=R) {
en=mid;
l=mid+1;
} else {
r=mid-1;
}
}
if(st!=-1 and en!=-1) {
update(1,1,n+1,i,query(1,1,n+1,st+1,en+1)%mod);
}
}
cout<<dp[1]<<endl;

}

Second solution

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 100;
const int mod = 1e9 + 7;
int l, r, n, ar[maxn], dp[maxn], sum_a[maxn], sum_dp[maxn];
vector<int> vc;

int32_t main(){
cin >> n >> l >> r;
for(int i = 0; i < n; i++)
cin >> ar[i];
for(int i = 0; i < n; i++){
sum_a[i + 1] = sum_a[i] + ar[i];

int st = lower_bound(vc.begin(), vc.end(), sum_a[i + 1] - r) - vc.begin();
int en = upper_bound(vc.begin(), vc.end(), sum_a[i + 1] - l) - vc.begin();

dp[i] = sum_dp[en] - sum_dp[st];
if(sum_a[i+1] >= l && sum_a[i+1] <= r)
dp[i]++;

dp[i] %= mod;
sum_dp[i + 1] = sum_dp[i] + dp[i];
vc.push_back(sum_a[i + 1]);

}
cout << dp[n - 1] << endl;
}