Cod sursa(job #174387)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 8 aprilie 2008 20:23:43
Problema Arbori indexati binar Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<stdio.h>
long x[100001],n,m,i,val,ad,poz,cod,st,dr,s,mi;
int main()
{
	freopen("aib.in","rt",stdin);
	freopen("aib.out","wt",stdout);
	scanf("%ld%ld",&n,&m);
	for(i=1;i<=n;i++)
	{ scanf("%ld",&val);
	  poz=i;
	  for(ad=1;poz<=n;ad<<=1)
	   if(ad&poz){x[poz]+=val;poz+=ad;}
	}
	for(;m;m--)
	{ scanf("%ld",&cod);
	  if(!cod)
	  { scanf("%ld%ld",&poz,&val);
	    for(ad=1;poz<=n;ad<<=1)
	     if(ad&poz){x[poz]+=val;poz+=ad;}
	    continue;
	  }
	  if(cod==1)
	  { scanf("%ld%ld",&st,&dr);
	    s=0;
	    poz=dr;
	    for(ad=1;poz;ad<<=1)
	     if(ad&poz){s+=x[poz];poz-=ad;}
	    poz=st-1;
	    for(ad=1;poz;ad<<=1)
	     if(ad&poz){s-=x[poz];poz-=ad;}
	    printf("%ld\n",s);
	    continue;
	  }
	  scanf("%ld",&val);
	  st=1;dr=n;
	  while(st<=dr)
	  { mi=(st+dr)>>1;
	    poz=mi;s=0;
	    for(ad=1;poz;ad<<=1)
	     if(ad&poz){s+=x[poz];poz-=ad;}
	    if(s==val){printf("%ld\n",mi);break;}
	    if(s<val)st=mi+1;
	    if(s>val)dr=mi-1;
	  }
	  if(st>dr)printf("-1\n");
	}
	fcloseall();
	return 0;
}