[ create a new paste ] login | about

Link: http://codepad.org/2MiT91wB    [ raw code | fork ]

C++, pasted on Mar 19:
#include<stdio.h>
const int MAX = (1 << 3);
int query;
int arr[2 * MAX], v[MAX],tme[2*MAX],vv[2*MAX];
void
B (int idx, int L, int R)
{
  if (L == R)
    {
      arr[idx] = v[L]; return;
    }
  int mid = (L + R) / 2;
  B (2 * idx + 1, L, mid);
  B (2 * idx + 2, mid + 1, R);
  arr[idx] = arr[2 * idx + 1] + arr[2 * idx + 2];
  return;
}

int Q1(int idx,int x,int y,int L,int R,int val,int tm);
void
U (int idx, int x, int y, int L, int R, int val)
{
  if (x > R || y < L)
    return;
  if (x <= L and R <= y)
    {
      arr[idx] += (R-L+1)*val;
      if((R-L) >0){
         int mid = (L + R) / 2;
         arr[2*idx] +=(mid-L+1)*val;
         arr[2*idx+1] +=(R-mid)*val;
         vv[2*idx] +=val;
         vv[2*idx + 1] +=val;
         vv[idx]=0;
//      printf("(L,mid,R)=(%d,%d,%d) %d:%d,%d\n",L,mid,R,arr[idx],arr[2*idx],arr[2*idx +1]);
      }
      else
      vv[idx]+=val;
      tme[idx]=query;
//      printf("idx=%d,%d:%d,val=%d,arr[idx]=%d\n",idx,L,R,val,arr[idx]);
      return;
    }
  int mid = (L + R) / 2;
  U (2 * idx , x, y, L, mid, val + vv[idx]);
  U (2 * idx + 1, x, y, mid + 1, R, val+ vv[idx]);
  //arr[idx] = Q1(1,L,mid,1,MAX,0,0) + Q1(1,mid+1,R,1,MAX,0,0);
  arr[idx]=arr[2*idx] + arr[2*idx +1];
//  printf("(l,R)=(%d,%d) %d,%d\n",L,R,arr[2*idx],arr[2*idx +1]);
}


int Q1(int idx,int x,int y,int L,int R,int val,int tm)
{
  if (x > R || y < L) return 0;
   if(x<=L and R<=y) return arr[idx]+ val;
   int mid=(L+R)/2;
   int z1,z2;
  if(tme[idx] > tme[2*idx]) z1=vv[idx];
 else z1=vv[2*idx];

  if(tme[idx] > tme[2*idx+1]) z2=vv[idx];
 else z2=vv[2*idx+1];

  return Q1 (2 * idx , x, y, L, mid,vv[idx]+val,tm) +
    Q1 (2 * idx + 1, x, y, mid + 1, R,vv[idx]+val,tm);
}

int
main ()
{
  int n, items = 1;
  scanf (" %d", &n);

  while (n--)
    {
       query++;
      int t, x, val,i;
      scanf (" %d", &t);
      for(i=0;i<2*MAX;i++) printf("%d,",arr[i]);
        printf("\n");
      
    if (t == 1)
	{
	  scanf (" %d %d", &x, &val);
      U(1,1,x,1,MAX,val);
      printf("%.7f\n",Q1(1,1,items,1,MAX,0,0)*1./items);
	}
    if (t == 2)
	{
	  scanf (" %d", &val);
	  items++;
      U(1,items,items,1,MAX,val);
      printf("%.7f\n",Q1(1,1,items,1,MAX,0,0)*1./items);
	}
      if (t == 3)
      {
         int lastele=Q1(1,items,items,1,MAX,0,0);
	//printf("lastele=%d\n",lastele);
         U(1,items,items,1,MAX,-lastele);
	     items--;
         printf("%.7f\n",Q1(1,1,items,1,MAX,0,0)*1./items);
      }
      for(i=0;i<2*MAX;i++) printf("%d,",arr[i]);
         printf("\n");
    }

  return 0;
}


Create a new paste based on this one


Comments: