Can someone help me out with what is wrong with this approach:-
‘’’
int n; cin >> n;
vector v(n);
fr(i, n)cin >> v[i];
set st;
for (int i = 0; i < n; i++)st.insert(i);
int q; cin >> q;
while (q–) {
int x, k; cin >> x >> k; x–;
auto it = st.lower_bound(x);
if (it == st.end()) {
cout << 0 << endl;
continue;
}
ll res = 0;
vector toerase;
for (auto i = it; i != st.end(); i++) {
int ind = *i;
int val = v[ind];
if (val > k) {
res += (ind - x) * k;
v[ind] -= k;
k = 0;
break;
}
if (val == k) {
res += (ind - x) * k;
v[ind] -= k;
toerase.pb(ind);
k = 0;
break;
}
else {
res += (ind - x) * v[ind];
k -= v[ind];
toerase.pb(ind);
}
}
for (int i = 0; i < toerase.size(); i++) {
st.erase(toerase[i]);
}
cout << res << endl;
}
‘’’
solution link
got it just made stupid mistake of using int instead of Long long 
AC
Very Nice problem, but certainly the difficulty shouldn’t be Cake-Walk.
I would love to watch any video editorial of this problem 
!
anyone explain algorithim of this question ??? .please explain easy steps
i am not able to understand when u are erasing elm when that ai=0 then in next query how u are getting deleted elment count also for distance .
arr={1,2,3,4,5}
x,k=4,4
x,k=3,5<----- then for it how u are counting 4 in b/w 3 and 5 as 4 is erased in previous query ??
Used fast output
True. I solved this problem very quickly, but I could see it occur as an easier C in CodeForces Div2. It’s definitely more of an ‘Easy’ problem, due to its heavy implementation and requirement of set and binary search, although it may not have the hardest idea.
can u explain the time complexity of the solution
Yes i have the same doubt!
To add all N elements to the set (or multiset), you’ll take (N log N) operations. To find the next element on the right it takes at most (log N) operations (binary search) per query and in case we exhaust all the places at given district removal is done in (log N) as well.
So in total it adds up to (N log N + Q log N) operations. There’s a mistake in the editorial as it states (N + Q log N) which is obviously incorrect, but it doesn’t change the whole thing miuch for the given constraints.
just simply subtracting the x from the current iterator gives u the distance between iterator and the district where citizens are dropped i.e - for x,k = 3,5 =>
it = 3;
as it->S = 3 which is not greater than k
d += (it->f-x)(it->s) = (3-3)(3) = 0;
k -= it->s => k = 2
as 4 is deleted so it = 5
for it = 5 , it->s > k
d += (5-3)*(2) = 4
here
thank you very much…
I found a solution with union-find data structure but I still getting WA! I made a tester and tested it with quiet a few testcases with the original constraints.Can someone figure out where I am getting wrong?Here is the link to my codeGOTHAM_Sol.cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
ll n;
cin>>n;
map<ll,ll>ad;
for(ll i=1;i<=n;i++)
{
ll c;
cin>>c;
ad.insert(pair<ll,ll>(i,c));
}
ll q;
cin>>q;
while(q–)
{
ll t,d;
cin>>t>>d;
map<ll,ll>::iterator itr;
itr=ad.lower_bound(t);
// cout<<“LOwerBOund-”<second<<endl;
ll ans=0;
if(itr==ad.end())
{
cout<<0<<endl;
}
else
{
for(;itr!=ad.end();itr++)
{
cout<<d<<"-"<<itr->second<<endl;
if(d==0)
{
break;
}
else if(itr->second>d&&d>0)
{
ans+=(itr->first-t)*d;
d=itr->second - d;
// cout<<d<<" ";
// map<ll,ll>::iterator it=itr;
// itr++;
ll t1=itr->first;
ll t2=itr->second-d;
ad.erase(itr->first);
ad.insert({t1,t2});
}
else
{
ans+= (itr->first-t)*itr->second;
d=d-itr->second;
ad.erase(itr->first);
// cout<<d<<" ";
}
}
cout<<ans<<endl;
}
return 0;
}
}
hello can someone please point out the error in my code. i have dry run the program few times. i am unable to find the error… I am complete beginner…
give a link or use ``` to format your code
Check this test-case
4
7 8 6 4
4
3 3
2 2
3 8
3 10
The answer should be 0,2,4,0
But my code was giving 0,2,0,0
so I corrected it.
Now it is giving 0,2,4,0
But still getting WA on submission.
Updated code