ENG  RUS Timus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

## Обсуждение задачи 1316. Биржа

Very good AC - 0.281 sec and 850K
Послано 12345 7 апр 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 (+)
Послано Dmitry 'Diman_YES' Kovalioff 7 апр 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 (+)
Послано Ilya Rasenstein (9 class) 12 апр 2005 22:13
I think, that he have used Fenwick tree
Re: Hmm... 850 Kbytes is really interesting (+)
Послано 12345 12 апр 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
Послано Burunduk1 9 апр 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 (+)
Послано Dmitry Tinitlov 3 авг 2006 19:26
Can you say book's names where these tree are described?
Re: Very good AC - 0.281 sec and 850K
Послано Hamdan Sultan 31 дек 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
Послано Insomnia 19 мар 2016 12:05