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 (+)
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 (+)
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
about 1400K of memory
PS: Good luck on the ROI, Ilya :)
Re: Very good AC - 0.281 sec and 850K
I've modified this solution...
Now it uses only 630K of memory!!!
(Random Trees are very useful :)
Re: Hmm... 850 Kbytes is really interesting (+)
Can you say book's names where these tree are described?
Re: Very good AC - 0.281 sec and 850K
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
i can't solve this problem.Please help... yu1178209138@hotmail.com