Обсуждение @ 1316. Биржа @ Timus Online Judge

Показать все сообщения Спрятать все сообщения

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
about 1400K of memory

PS: Good luck on the ROI, Ilya :)

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 Burunduk1 9 апр 2006 04:01

I've modified this solution...
Now it uses only 630K of memory!!!
(Random Trees are very useful :)

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

i can't solve this problem.Please help... yu1178209138@hotmail.com

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