Segment Tree Spoj Problem

editorial
1

Hello,
Recently I attempted the following problem on SPOJ

HELPR2D2

I worked on it for quite sometime and figured it was an easy Binary Search/Greedy problem. Binary Search on the ships and allocate containers to the one with the relevant lowest index was my approach.

However, after a few WA attempts, I looked at the comments and everywhere it was about AVL Trees or Segment Trees. I don’t understand why a simple Binary Search has got anything to do with Segment Trees!

Can anybody please spare sometime to take a look at this problem and point out the flaw in greedy algorithm, or rather why is segtree more essential? Thanks in advance for help!

Here’s my WA attempt with binary search:

const int N = 1000005;
typedef long long ll;

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;
    }
}