It needs two arrays of 1000000 longint  at least...
Can be less??

I uses index tree - one array[1..1000000]of longint;
:)

How to only use one array??

try to study AVL or Red-Black Trees or Binary Indexed(?) Trees
to find out how...

I used Binary Index Tree, but it needs two arrays of 1000000 longint....

one records the value of the node
the other records the amout of the nodes and its children...

Only one array :
A[i]:amount of "BID" with price bigger than i

Edited by author 16.09.2004 11:17

It is right? :

One array: A[i]: amout of "BID" with the price I

the sum of A[1]+A[2]....+A[k-1] is the amout of pigs whose prices are smaller than K


Edited by author 16.09.2004 21:56

Sorry, it's my mistake:)
A[i]:amount of "BID" with price lower or equal to i

My solution: (N log N)
  A[i]: the amout of  price I
  SALE x k : Sum(Ax+Ax+1+Ax+2...AN) or K

But WrongAnswer On test#5..... Any BUG??

const
  maxn=1000000;
var
  money,amout,price,bids,y:longint;
  x:real;
  ch,ch0:char;
  c:array[0..maxn] of longint;

function Lowbitd(x: longint): longint;
begin
    Lowbitd:=x and (x xor (x - 1));
end;

function Sum(x: longint): longint;
var
    res:longint;
begin
    res:= 0;
    while x > 0 do
    begin
        res:= res + C[x];
        x:= x - Lowbitd(x);
    end;
    Sum:= res;
end;

procedure Modifyd(p, deltas: longint);
begin
    while p <= maxn do
    begin
       C[p]:= C[p] + deltas;
       p:= p + Lowbitd(p);
    end;
end;

begin
  fillchar(c,sizeof(c),0);
  bids:=0;  money:=0;
  while not eof do
  begin
    read(ch0);
    if ch0='Q' then break;  ch:=ch0;
    while ch<>' ' do  read(ch);
    if ch0='S' then
    begin
      read(x,amout);  readln;
      price:=trunc(x*100);
      y:=Sum(price-1);
      y:=bids-y;
      if y<amout then money:=money+y
      else money:=money+amout;
    end
    else begin
           read(x);  readln;
       price:=trunc(x*100);
       if ch0='B' then
       begin
         inc(bids);
         Modifyd(price,1);
        end
        else if ch0='D' then
                 begin
               dec(bids);
           Modifyd(price,-1);
         end;
        end;
  end;
  x:=money*0.01;
  writeln(x:0:2);
end.



Edited by author 17.09.2004 18:14