Cod sursa(job #436)

Utilizator raula_sanChis Raoul raula_san Data 11 decembrie 2006 11:31:36
Problema Datorii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<cstdio>

#define dim 15001

using namespace std;

long N, M, op, a, b, A[dim], H[dim];

long zbit(long x)
{
     return
           x ^ (x & (x-1));
}

long quest(long dr)
{
     long s = 0;
     
     while(dr)
     {
              s += H[dr];
              dr -= zbit(dr);
     }
     
     return s;
}

int main()
{
    freopen("datorii.in", "r", stdin);
    freopen("datorii.out", "w", stdout);
    
    scanf("%ld %ld", &N, &M);

    long i, st, dr;
    
    for(i=1; i<=N; ++i)
    {
             scanf("%ld", A + i);
             A[i] += A[i-1];
    }
    
    for(i=1; i<=N; ++i)
    {
             st = i - zbit(i) + 1;
             dr = i;
             
             H[i] = A[dr] - A[st-1];
    }
    
    for(i=1; i<=M; ++i)
    {
             scanf("%ld %ld %ld", &op, &a, &b);
             
             if(!op) // achita o valoare b din restanta zilei a
             {
                     while(a <= N)
                     {
                             H[a] -= b;
                             a += zbit(a);
                     }
             }
             
             else // suma restantelor din zilele a ... b
                  printf("%ld\n", quest(b) - quest(a-1));
    }
    
    fclose(stdin);
    fclose(stdout);
    
    return 0;
}