Hello. I am trying to attempt the following problem
https://www.spoj.com/problems/HELPR2D2/
After trying for a while, I figured the lowest index of each ship with capacity more than C can be picked by just binary searching all the ships(lower_bound) and subtract the respective volume. However, after a few WA attempts, I googled if I can find a solution.
There is no explanation though, but I can see only segtree implementation and I can't get my head around why its a segtree problem(or rather, why not just bsearch). Can anybody help me point out the flaw in binary search approach. It looks so obvious to me that it is binary search(but it isn't). Thanks in advance for any help. Here's my bsearch WA attempt:
int main()
{
int t;
cin >> t;
while(t--)
{
vector<ll> a;
int k, n;
cin >> k >> n;
set<ll> s;
a.assign(100005, k);
char c;
int r, v;
ll used = 0, usedvol = 0;
char lead[16];
forn(i, n)
{
scanf("%s", lead);
if(lead[0] != 'b')
{
r = 1;
v = atoi(lead);
}
else
{
cin >> r >> v;
n-=r-1;
}
forn(i, r)
{
int lowidx = std::lower_bound(a.begin(), a.end(), v) - a.begin();
a[lowidx]-=v;
if(s.find(lowidx) == s.end())
{
used++;
usedvol += v;
s.insert(lowidx);
}
else
{
usedvol += v;
}
}
}
cout << used << " " << used * k - usedvol << endl;
}
}
