Cod sursa(job #188478)

Utilizator c_iulyanCretu Iulian c_iulyan Data 8 mai 2008 16:54:12
Problema Datorii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<cstdio>
using namespace std;
typedef long long l;

long n,m,a[15005];
l t[50000];

void makeai(long i,long j,long nd)
{
if(i==j) t[nd]=a[i];
else {
     long m=(i+j)/2;
     makeai(i,m,nd*2);
     makeai(m+1,j,nd*2+1);
     t[nd]=t[nd*2]+t[nd*2+1];
     }
}

void upg(long i,long j,long x,long y,long nd)
{
t[nd]-=y;

if(i==j) return;

long m=(i+j)/2;
if(x<=m)
   upg(i,m,x,y,nd*2);
else
   upg(m+1,j,x,y,nd*2+1);
}

l sum(int i,int j,int nd,int x,int y)
{
if(x<=i&&j<=y) return t[nd];

long m=(i+j)/2;
l s=0;
if(x<=m)
  s+=sum(i,m,nd*2,x,y);
if(m<y)
  s+=sum(m+1,j,nd*2+1,x,y);

return s;
}

void rd()
{
scanf("%ld%ld",&n,&m);
long i;
for(i=1;i<=n;i++)
   scanf("%ld",&a[i]);

makeai(1,n,1);

long p,x,y;
for(i=1;i<=m;i++)
   {
   scanf("%ld%ld%ld",&p,&x,&y);
   if(p==0)
      upg(1,n,x,y,1);
   else
      printf("%lld\n",sum(1,n,1,x,y));
   }
}

int main()
{
freopen("datorii.in","r",stdin);
freopen("datorii.out","w",stdout);

rd();

return 0;
}