➤ Problem Link : 1042D. Petya and Array
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll divMerge(ll i, ll j, ll arr[],ll t)
{
if(i==j)
{
if(arr[i]< t)
return 1;
return 0;
}
ll ans=0,k;
if(i<j)
{
k=(i+j)/2;
ans = divMerge(i,k,arr,t);
ans += divMerge(k+1,j,arr,t);
map<ll,ll> mp;
ll sum=0;
for(ll m=k+1;m<=j;m++)
{
sum+=arr[m];
mp[sum]++;
}
auto it = mp.begin();
auto it2=it;
it2++;
for(;it2!=mp.end();it++,it2++)
(*it2).second += (*it).second;
sum=0;
for(ll m=k;m>=i;m--)
{
sum+=arr[m];
it = mp.upper_bound(t-sum-1);
if(it==mp.begin())
continue;
--it;
ans+=(*it).second;
}
}
return ans;
}
int main()
{
ll n,t;
cin>>n>>t;
ll arr[n];
for(ll i=0;i<n;i++)
cin>>arr[i];
cout<<divMerge(0,n-1,arr,t);
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
➤ Problem Link : 1042D. Petya and Array
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll divMerge(ll i, ll j, ll arr[],ll t)
{
if(i==j)
{
if(arr[i]< t)
return 1;
return 0;
}
ll ans=0,k;
if(i<j)
{
k=(i+j)/2;
ans = divMerge(i,k,arr,t);
ans += divMerge(k+1,j,arr,t);
map<ll,ll> mp;
ll sum=0;
for(ll m=k+1;m<=j;m++)
{
sum+=arr[m];
mp[sum]++;
}
auto it = mp.begin();
auto it2=it;
it2++;
for(;it2!=mp.end();it++,it2++)
(*it2).second += (*it).second;
sum=0;
for(ll m=k;m>=i;m--)
{
sum+=arr[m];
it = mp.upper_bound(t-sum-1);
if(it==mp.begin())
continue;
--it;
ans+=(*it).second;
}
}
return ans;
}
int main()
{
ll n,t;
cin>>n>>t;
ll arr[n];
for(ll i=0;i<n;i++)
cin>>arr[i];
cout<<divMerge(0,n-1,arr,t);
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.