What can I do on Memory optimize ??

Posted by

tbtbtb 14 Sep 2004 21:02

It needs two arrays of 1000000 longint at least...

Can be less??

Try another way. I used RB-Trees to solve this problem.

Re: Try another way. I used RB-Trees to solve this problem.

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

:)

Re: Try another way. I used RB-Trees to solve this problem.

Posted by

tbtbtb 15 Sep 2004 19:53

How to only use one array??

Re: Try another way. I used RB-Trees to solve this problem.

Posted by

Macarie 15 Sep 2004 20:09

try to study AVL or Red-Black Trees or Binary Indexed(?) Trees

to find out how...

Re: Try another way. I used RB-Trees to solve this problem.

Posted by

tbtbtb 15 Sep 2004 20:36

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...

Re: Try another way. I used RB-Trees to solve this problem.

Only one array :

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

*Edited by author 16.09.2004 11:17*

Re: Try another way. I used RB-Trees to solve this problem.

Posted by

tbtbtb 16 Sep 2004 21:55

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*

Re: Try another way. I used RB-Trees to solve this problem.

Sorry, it's my mistake:)

A[i]:amount of "BID" with price lower or equal to i

Re: Try another way. I used RB-Trees to solve this problem.

Posted by

tbtbtb 17 Sep 2004 18:13

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*