|
|
вернуться в форумПоказать все сообщения Спрятать все сообщения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 |
|
|