CodeChef submission 108175 (C++ 4.0.0-8) plaintext list. Status: RE, problem H5, contest OCT09. By porsh (Shishir Mittal), 2009-10-11 01:01:00.
#include<iostream>
using namespace std;
int p2;
struct LINE{
  int len;
  int stIndex;
}line[205];
 
int binarySearch(struct LINE arr[],int low,int high, int x){
  int mid,i,k;
  while(low < high){
	mid = (low + high + 1)/2;
	if(x >= arr[mid].stIndex)
	  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[50000],lineCtr=1,length,wordIndex,newLen,lineNo,delta,charNo,w;
  long long sum[50000];
  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].stIndex = 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].stIndex = i; 
	  }
	}
	line[lineCtr].len = length;
	line[lineCtr+1].stIndex = 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;
	  word[p2+i].S = arr[i+1];
	}
	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 +1].key - 1;
		word[i].S = sum[word[i].key] - sum[word[i].key-h];
	  }
	}
	  
	
	
	//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 && lineNo > 1){
		  wordIndex = line[lineNo].stIndex;
		  charNo = M - (getSum(line[lineNo].stIndex-1) - getSum(line[lineNo-1].stIndex-1) + line[lineNo].stIndex - line[lineNo-1].stIndex);
		  w = wordSearch(line[lineNo].stIndex,line[lineNo +1].stIndex-1,charNo);
		  line[lineNo].stIndex = w+1;
		  charNo = M - (getSum(line[lineNo+1].stIndex-1) - getSum(line[lineNo].stIndex-1) + line[lineNo+1].stIndex - line[lineNo].stIndex);
		  while(lineNo<lineCtr && (w = wordSearch(line[lineNo+1].stIndex,line[lineNo +2].stIndex-1,charNo)) != line[lineNo+1].stIndex-1){
			lineNo++;
			line[lineNo].stIndex = w+1;
			charNo = M - (getSum(line[lineNo+1].stIndex-1) - getSum(line[lineNo].stIndex-1) + line[lineNo+1].stIndex - line[lineNo].stIndex);
		  }
		  if(line[lineCtr].stIndex == N+1){
			//cout<<"afa"<<endl;
			lineCtr--;
		  }
 		} 
		else{
		  charNo = M - (getSum(wordIndex-1) - getSum(line[lineNo].stIndex-1) + wordIndex - line[lineNo].stIndex);
		//if(delta < 0) lineNo++;
		  while((w = wordSearch(wordIndex,line[lineNo +1].stIndex-1,charNo)) != line[lineNo+1].stIndex-1){
			//if(getSum(w) - getSum(line[lineNo].stIndex) + w - line[lineNo].stIndex >= M-1){
			//cout<<"w="<<w<<endl;
			charNo = M - (getSum(line[lineNo+1].stIndex - 1) - getSum(w) + line[lineNo+1].stIndex -w -1);
			lineNo++;
			if(lineNo > lineCtr){
			  lineCtr = lineNo;
			  line[lineCtr+1].stIndex = N+1;
			  //break;
			}
			wordIndex = line[lineNo].stIndex;
			line[lineNo].stIndex = w+1;
			if(wordIndex == N+1)
			  break;
			
		  }
		}
		break;  
		default: cout<<"Error parsing input\n";
	  }
	}
	printf("\n");
  }
  return 0;
}