HackerEarth Partitions problem solution YASH PAL, 31 July 2024 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. #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("%lldn",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 100000000000000typedef 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_boundlli 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 longusing 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;} coding problems