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

Very good AC - 0.281 sec and 850K
Posted by 12345 7 Apr 2005 02:09
My program uses only 850K of memory!!!
Two days of troubles and the best solution was written!
If you are intrested in it leave your mail here.
Hmm... 850 Kbytes is really interesting (+)
Posted by Dmitry 'Diman_YES' Kovalioff 7 Apr 2005 08:49
I've solved this problem via interval tree, but it uses 4 Mbytes. I don't need your code, but could you explain your algorithm? My e-mail is dimanyes@yahoo.com
Re: Hmm... 850 Kbytes is really interesting (+)
Posted by Ilya Rasenstein (9 class) 12 Apr 2005 22:13
I think, that he have used Fenwick tree
Re: Hmm... 850 Kbytes is really interesting (+)
Posted by 12345 12 Apr 2005 22:42
No :)
This solution uses Cartesian tree.
My best solution which uses Fenwick's tree uses

PS: Good luck on the ROI, Ilya :)
Re: Very good AC - 0.281 sec and 850K
Posted by Burunduk1 9 Apr 2006 04:01
I've modified this solution...
Now it uses only 630K of memory!!!
(Random Trees are very useful :)
Re: Hmm... 850 Kbytes is really interesting (+)
Posted by Dmitry Tinitlov 3 Aug 2006 19:26
Can you say book's names where these tree are described?
Re: Very good AC - 0.281 sec and 850K
Posted by Hamdan Sultan 31 Dec 2014 18:55
can i do it without trees ? like this
#include<iostream>
#include<string>
using namespace std;
void limit_to_two_num(float &price)
{
price=price*100;
price=static_cast<int>(price);
price=(price)/100;
}
void main()
{
int check=0,quantity,length=0;
string str="\0";
float price;
float profit=0;
float arr[100000];
while(str!="QUIT" && check!=100000)
{
cin>>str;
if(str=="BID")
{
cin>>price;
limit_to_two_num(price);
arr[length++]=price;
check++;
}
else if(str=="DEL")
{
cin>>price;
limit_to_two_num(price);
for(int i=0;i<length;i++)
{
if(arr[i]==price)
{
for(int j=i;j<length-1;j++)
{
arr[j]=arr[j+1];
}
length--;
break;
}
}
check++;
}
else if(str=="SALE")
{
cin>>price;
limit_to_two_num(price);
cin>>quantity;
for(int i=0;i<length;i++)
{
if(arr[i]>=price)
{
profit=profit+0.01;
}
}
}
}
cout<<"Total profit: "<<profit<<endl;
}
Re: Very good AC - 0.281 sec and 850K
Posted by Insomnia 19 Mar 2016 12:05