Use long long

for lazy node propagation I did tree[n]+=(end-start+1)*lazy[n];
when start and end were integers. tree[n]+=(end-start+1)*(1ll)*lazy[n]; corrected error.

i have used long long  and   scanf
still wa
who can help me?plz  0.0

OMG, standart interval tree gives TLE 6. It's terrible! Why?!

double check lazy calculations

Edited by author 25.10.2012 03:55

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

use cin.sync_with_stdio(false)

Btw, WA5 was due to int instead of int64_t

What can cause a "wrong answer" in 7-th test?

Could anyone help me with test number 3?
I am having WA for some time and can't figure out what seems to be the problem.