Where is bug?
WA6:
#include <iostream>
#pragma comment(linker, "/STACK:46777216")
#include <vector>
using namespace std;
#define ll int64_t
const int MAXN = 50005;
ll t[4*MAXN], add[4*MAXN], sz[MAXN];
ll n, q, x, cnt;
ll y, z, value[MAXN];
char c[15];
vector <ll> g[MAXN];
ll p[MAXN], pos[MAXN];
void init(ll v, ll tl, ll tr)
{
if(tl == tr) add[v]=(ll)0, t[v]=value[tl];
else
{
ll m=(tl+tr)/2;
init(2*v, tl, m);
init(2*v+1, m+1,tr);
add[v]=(ll)0, t[v]=t[2*v]+t[2*v+1];
}
}
ll sum(ll v, ll tl, ll tr, ll l, ll r)
{
if(tl == l && tr == r) return t[v];
else
{
ll m = (tl + tr) /2 ;
ll a = add[v] * (ll)(r-l+1);
if(r<=m) return a+sum(2*v, tl, m, l, r);
if(l>m) return a+sum(2*v + 1, m+1, tr, l, r);
return a+sum(2*v, tl, m, l, m) + sum(2*v + 1, m+1, tr, m+1, r);
}
}
void update(ll v, ll tl, ll tr, ll l, ll r, ll val)
{
if(tl == l && tr == r) add[v]+=val, t[v]+=val*(ll)(tr-tl+1);
else
{
ll m = (tl + tr) /2;
if(r<=m) update(2*v , tl, m, l, r, val);
else
{
if(l>m) update(2*v + 1, m+1, tr, l, r, val);
else update(2*v , tl, m, l, m, val), update(2*v + 1, m+1, tr, m+1, r, val);
}
t[v]=t[2*v]+t[2*v +1];
}
};
void dfs(ll v, ll par = -1)
{
p[v] = par, pos[v] = ++cnt, sz[v] = (ll)1;
for (ll i = 0; i < (ll) g[v].size(); i++)
{
ll to = g[v][i];
if (to == par) continue;
dfs(to, v);
sz[v] += sz[to];
}
}
int main()
{
scanf("%lld %lld %lld", &n, &q, &value[1]);
for (ll i = 2; i <= n; i++)
{
scanf("%lld %lld\n", &x, &value[i]);
x++;
g[x].push_back(i);
g[i].push_back(x);
}
cnt = 0;
dfs(1);
init(1, 1, n);
for (ll i = 1; i <= q; i++)
{
scanf("%s %lld %lld %lld\n",&c, &x, &y, &z);
x++;
if (c[0] == 'e')
{
ll salary=sum(1,1,n,pos[x],pos[x]);
if(salary<y) update(1,1,n,pos[x],pos[x],z);
}
else
{
ll departament = sum(1,1,n,pos[x],pos[x]+sz[x]-1);
if(departament<y*sz[x]) update(1,1,n,pos[x],pos[x]+sz[x]-1,z);
}
}
for(ll i=1;i<=n;i++)
{
ll salary=sum(1,1,n,pos[i],pos[i]);
printf("%lld", salary);
if(i<n) printf("\n");
}
return 0;
}
WA8:
#include <iostream>
#pragma comment(linker, "/STACK:46777216")
#include <vector>
using namespace std;
#define ll unsigned long long
const int MAXN = 50005;
ll sum[MAXN], add[MAXN], sz[MAXN], L[MAXN], R[MAXN];
int n, q, x, cnt, c;
ll y, z, value[MAXN], len;
char str[15];
vector <int> g[MAXN];
int p[MAXN], pos[MAXN], ind[MAXN];
void Create()
{
len=(ll)1;
while(len*len<n) len++;
if(len*len>n) len--;
c= n / len;
for(int i=1;i<=c;i++) L[i]=(ll)(1+len*(i-1)), R[i]=(ll)(len*i);
if(c*len<n) c++, L[c]=R[c-1]+1, R[c]=n;
for(int i=1;i<=c;i++)
{
sum[i]=(ll)0, add[i]=(ll)0;
for(int j=L[i];j<=R[i];j++) sum[i]+=value[j], ind[j]=i;
}
}
void Update(int l, int r, ll val)
{
int k1=ind[l];
int k2=ind[r];
for(int i=k1+1;i<=k2-1;i++) sum[i]+=val*(ll)(R[i]-L[i]+1), add[i]+=val;
if(k1==k2)
{
for(int i=l;i<=r;i++) value[i]+=val, sum[k1]+=val;
}
else
{
if(l==L[k1]) sum[k1]+=val*(ll)(R[k1]-L[k1]+1), add[k1]+=val;
else
{
for(int i=l;i<=R[k1];i++) value[i]+=val, sum[k1]+=val;
}
if(r=R[k2]) sum[k2]+=val*(ll)(R[k2]-L[k2]+1), add[k2]+=val;
else
{
for(int i=L[k2];i<=r;i++) value[i]+=val, sum[k2]+=val;
}
}
}
ll Sum(int l, int r)
{
int k1=ind[l];
int k2=ind[r];
ll res=(ll)0;
for(int i=k1+1;i<=k2-1;i++) res+=sum[i];
if(k1==k2)
{
for(int i=l;i<=r;i++) res+=value[i];
res+=add[k1]*(ll)(r-l+1);
}
else
{
for(int i=l;i<=R[k1];i++) res+=value[i];
res+=add[k1]*(ll)(R[k1]-l+1);
for(int i=L[k2];i<=r;i++) res+=value[i];
res+=add[k2]*(ll)(r-L[k2]+1);
}
return res;
}
void Dfs(int v, int par = -1)
{
p[v] = par, pos[v] = ++cnt, sz[v] = (ll)1;
for (int i = 0; i < (int) g[v].size(); i++)
{
int to = g[v][i];
if (to == par) continue;
Dfs(to, v);
sz[v] += sz[to];
}
}
int main()
{
scanf("%d%d%lld\n", &n, &q, &value[1]);
for (int i = 2; i <= n; i++)
{
scanf("%d%lld\n", &x, &value[i]);
x++;
g[x].push_back(i);
g[i].push_back(x);
}
Dfs(1);
Create();
scanf("\n");
for (int i = 1; i <= q; i++)
{
scanf("%s%d%lld%lld\n",&str, &x, &y, &z);
x++;
if (str[0] == 'e')
{
ll salary=Sum(pos[x],pos[x]);
if(salary<y) Update(pos[x],pos[x],z);
}
else
{
ll departament = Sum(pos[x],pos[x]+sz[x]-1);
if(departament<y*sz[x]) Update(pos[x],pos[x]+sz[x]-1,z);
}
}
for(int i=1;i<=n;i++)
{
ll salary=Sum(pos[i],pos[i]);
printf("%lld", salary);
if(i<n) printf("\n");
}
return 0;
}
Edited by author 10.03.2018 23:40