CodeChef submission 108546 (C++ 4.0.0-8) plaintext list. Status: AC, problem H5, contest OCT09. By fernandoshao (Xuancheng Shao), 2009-10-11 09:46:26.
#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
int t, m, n, numline;
int sum[50001];
int a[50001];
int line[201];
 
void increase(int id, int value)
{
  int k = 0;
  while (true)
    {
      if ((id & (1 << k)) == 0)
	{
	  int pos = ((id >> k) | 1) << k;
	  if (pos <= n)
	    sum[pos] += value;
	  else
	    break;
	}
      k++;
    }
}
 
int getsum(int id)
{
  id++;
  int k = 0;
  int ans = sum[id];
  while (true)
    {
      if ((id & (1 << k)) > 0)
	{
	  int pos = ((id >> k) - 1) << k;
	  ans += sum[pos];
	}
      else
	if (id < (1 << k))
	  break;
      k++;
    }
  return ans;
}
 
int findword(int id, int p, int r)
{
  if (p == r) return p;
  int q = (p+r)/2;
  if (id <= line[q]) return findword(id, p, q);
  return findword(id, q+1, r);
}
 
int getlastword(int prev, int prevsum, int p, int r)
{
  //cout << "prev=" << prev << " prevsum=" << prevsum << " p=" << p << " r=" << r << endl;
  if (p == r) return p;
  int q = (p+r)/2+1;
  if (getsum(q)-prevsum+q-prev-1 > m) return getlastword(prev, prevsum, p, q-1);
  return getlastword(prev, prevsum, q, r);
}
 
void fillline(int r, bool flag)
{
  //if (r > numline) numline = r;
  int lastword = getlastword(line[r-1], getsum(line[r-1]), line[r-1]+1, n-1);
  if (flag && r <= numline && lastword == line[r]) return;
  line[r] = lastword;
  if (lastword == n-1)
    numline = r;
  else
    fillline(r+1, true);
}
 
int main()
{
  cin >> t;
  for (int casenum = 0; casenum < t; casenum++)
    {
      cout << "Case #" << casenum+1 << ":" << endl;
      cin >> m;
      cin >> n;
 
      for (int i = 0; i <= n; i++) sum[i] = 0;
      for (int i = 0; i < n; i++)
	{
	  cin >> a[i];
	  increase(i, a[i]);
	}
 
      for (int i = 0; i < 201; i++) line[i] = -1;
      fillline(1, true);
 
      //cout << "numline=" << numline << endl;
 
      string com;
      cin >> com;
      while (com != "E")
	{
	  int id, newlen;
	  if (com[0] == 'I')
	    {
	      cin >> id;
	      cout << findword(id-1, 1, numline) << endl;
	    }
	  else
	    {
	      cin >> id >> newlen;
	      id--;
	      increase(id, newlen-a[id]);
 
	      int r = findword(id, 1, numline);
	      if (r > 1 && newlen < a[id] && id == line[r-1]+1) 
		fillline(r-1, false);
	      else
		fillline(r, true);
	      
	      a[id] = newlen;
	    }
	  cin >> com;
	}
      cout << endl;
    }
  return 0;
}