CodeChef submission 108212 (C++ 4.0.0-8) plaintext list. Status: WA, problem H5, contest OCT09. By porsh (Shishir Mittal), 2009-10-11 02:02:32.
#include<iostream>
using namespace std;
int p2;
int line[205];
 
int binarySearch(int arr[],int low,int high, int x){
  int mid,i,k;
  while(low < high){
	mid = (low + high + 1)/2;
	if(x >= arr[mid])
	  low = mid;
	else
	  high = mid -1;
  }
  return low;
}
 
struct wordNode{
  int key,S;
}word[132000];
 
void updateWordTree(int wordIndex, int delta){
  int index = p2 + wordIndex - 1;
  word[index].S += delta;
  do{
	if(index%2 == 0){
	  word[index/2].S += delta;
	}
	index = index/2;
  }while(index > 1);
  
}
int getSum(int wordIndex){
  if(wordIndex== 0)
	return 0;
  int i=1,k,sum=0;
  while(i<p2){
	if(wordIndex <= word[i].key)
	  i = 2*i;
	else{
	  sum += word[i].S;
	  i = 2*i+1;
	}
  }
  sum += word[i].S;
  //cout<<"getSum("<<wordIndex<<") = "<<sum<<endl;
  return sum;
}
 
int wordSearch(int lowWordIndex, int highWordIndex, int charNo){
  //cout<<lowWordIndex<<","<<highWordIndex<<endl;
  int midSum,low = lowWordIndex,high = highWordIndex,mid, s= getSum(lowWordIndex-1);
  while(low < high){
	mid = (low + high)/2;
	midSum = getSum(mid);
	if(charNo > midSum - s + mid - lowWordIndex+1)
	  low = mid +1;
	else
	  high = mid;
  }
  if(getSum(high) - s + high - lowWordIndex <= charNo)
	return high;
  else
	return high-1;
}
	
  
	  
	
int main(){
  int i,T,kase,k,M,N,h,arr[132000],lineCtr,length,wordIndex,newLen,lineNo,delta,charNo,w;
  long long sum[132000];
  scanf("%d",&T);
  for(kase=1;kase<=T;kase++){
	printf("Case #%d:\n",kase);
	//input M, N, ai's.
	scanf("%d %d",&M,&N);
	for(p2=1;p2<N;p2*=2);
	lineCtr=1;
	sum[0] = 0;
	//form line array with the indices of first word
	line[lineCtr] = 1;
	
	scanf("%d",&arr[1]);
	sum[1] = arr[1] + sum[0];
	length = arr[1];
	
	for(i=2;i<=N;i++){
	  scanf("%d",&arr[i]);
	  sum[i] = arr[i] + sum[i-1];
	  if(length + 1 + arr[i] <=M)
		length += 1+arr[i];
	  else{
		//line[lineCtr].len = length;
		length = arr[i];
		lineCtr++;
		line[lineCtr]= i; 
	  }
	}
	//line[lineCtr].len = length;
	line[lineCtr+1] = N+1;
	//line[lineCtr+1].len = 0;
	  
	//form word tree to find 'sum till ith word in theta(log N) time'.
	for(i=N+1;i<=p2;i++){
	  arr[i] = 0;
	  sum[i] = sum[i-1];
	}
	for(i=0;i<p2;i++){
	  word[p2+i].key = i+1;
	  //cout<<word[p2+i].key<<" ";
	  word[p2+i].S = arr[i+1];
	}
	//cout<<endl;
	for(k=p2/2,h=1;k>=1;k = k/2,h++){
	  
	  for(i=k;i<2*k;i++){
		word[i].key = (word[2*i].key + word[2*i+1].key)/2;
		//cout<<word[i].key<<" ";
		word[i].S = sum[word[i].key] - sum[word[i].key-h];
	  }
	  //cout<<endl;
	}
	  
	
	
	//Input Query
	char ch[2];
	while(scanf("%1s",ch), ch[0] != 'E'){
	  //if Query is to output #line, binary search in line array.
	  switch(ch[0]){
		
		case 'I': scanf("%d",&wordIndex);
		printf("%d\n",binarySearch(line,1 , lineCtr, wordIndex));
		break;
		//if Query is changing wordLength,
		case 'C': scanf("%d %d",&wordIndex,&newLen);
		//First find the #line,
		lineNo = binarySearch(line,1 , lineCtr, wordIndex);
		//cout<<"lineNo:"<<lineNo<<endl;
		delta = newLen - word[p2+wordIndex-1].S;
		//cout<<"delta="<<delta<<endl;
		updateWordTree(wordIndex, delta);
		if(delta==0)
		  break;
		else if(delta < 0){
		  if(lineNo > 1 && (wordIndex == line[lineNo])){
			charNo = M - (getSum(line[lineNo]-1) - getSum(line[lineNo-1]-1) + line[lineNo] - line[lineNo-1]);
			w = wordSearch(line[lineNo],line[lineNo +1]-1,charNo);
			line[lineNo] = w+1;
		  }
		  charNo = M - (getSum(line[lineNo+1]-1) - getSum(line[lineNo]-1) + line[lineNo+1] - line[lineNo]);
		  while(lineNo<lineCtr && (w = wordSearch(line[lineNo+1],line[lineNo +2]-1,charNo)) != line[lineNo+1]-1){
			lineNo++;
			line[lineNo] = w+1;
			charNo = M - (getSum(line[lineNo+1]-1) - getSum(line[lineNo]-1) + line[lineNo+1] - line[lineNo]);
		  }
		  if(line[lineCtr] == N+1)
			lineCtr--;
		  
 		} 
		else{
		  charNo = M - (getSum(wordIndex-1) - getSum(line[lineNo]-1) + wordIndex - line[lineNo]);
		//if(delta < 0) lineNo++;
		  while((w = wordSearch(wordIndex,line[lineNo +1]-1,charNo)) != line[lineNo+1]-1){
			charNo = M - (getSum(line[lineNo+1] - 1) - getSum(w) + line[lineNo+1] -w -1);
			lineNo++;
			if(lineNo > lineCtr){
			  lineCtr = lineNo;
			  line[lineCtr+1] = N+1;
			  //break;
			}
			wordIndex = line[lineNo];
			line[lineNo] = w+1;
			if(wordIndex == N+1)
			  break;
			
		  }
		}
		break;  
		default: cout<<"Error parsing input\n";
	  }
	}
	printf("\n");
  }
  return 0;
}