Spoj Problem HELPR2D2 solution

Revision en1, by drunk_philosopher, 2019-07-22 17:35:55

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;
    }
}
Tags #segment tree, #binary search

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English drunk_philosopher 2019-07-22 17:35:55 1704 Initial revision (published)