ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1316. Electronic Auction

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.
Posted by Grebnov Ilya[Ivanovo SPU] 14 Sep 2004 21:18
Re: Try another way. I used RB-Trees to solve this problem.
Posted by Saturn (HUS) 15 Sep 2004 09:48
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.
Posted by Saturn (HUS) 15 Sep 2004 23:37
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.
Posted by Saturn (HUS) 17 Sep 2004 04:24
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
if ch0='Q' then break;  ch:=ch0;
if ch0='S' then
begin
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
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