Cod sursa(job #1549730)
Utilizator | Data | 12 decembrie 2015 18:22:01 | |
---|---|---|---|
Problema | Datorii | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.58 kb |
#include <iostream>
#include <cstdio>
using namespace std;
long long int A[150000][1500],i,j,k,n,m,p,poz,val,s,t;
int main()
{
freopen("datorii.in","r",stdin);
freopen("datorii.out","w",stdout);
scanf("%lli %lli",&n,&m);
for (i=0;i<n;i++)
{
scanf("%lli",&A[0][i]);
}
k=n/2;
for (i=1;(1<<i)<n;i++)
{
for (j=0;j<k;j++)
{
A[i][j]=A[i-1][j*2]+A[i-1][j*2+1];
}
k>>=1;
}
/* for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
cout<<A[i][j]<<" ";
}
cout<<'\n';
}
cout<<'\n';
*/
for (i=1;i<=m;i++)
{
scanf("%lli %lli %lli",&p,&poz,&val);
poz--;
if (p==0)
{
j=0;
while (A[j][poz])
{
A[j][poz]-=val;
j++;
poz>>=1;
}
}
else
{
s=0;
val--;
while (poz<=val)
{
j=0;
t=poz;
while ((t+(1<<(j+1)))<val&&(t%2==0))
{
j++;
t>>=1;
}
s+=A[j][t];
poz+=(1<<j);
// cout<<s<<" "<<poz<<" ";
}
printf("%lli \n",s);
}
}
/* for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
cout<<A[i][j]<<" ";
}
cout<<'\n';
}
*/
}