No. This is the lower bound, since you have to read the edges anyways.

You can use structure Heap or Interval Tree ( because the value of the elements is rather small ).
Heap : O(NlogM)
Interval tree : O(N log(Max_Value) ).
Interval tree also can give you the k-th smallest value in log (Max_value).

Yes... and with little bit of optimization, one can get AC in half of that time... :)

Edited by author 20.03.2016 19:06

I implemented that but I have WA 5. What's in this test?

Thank you
And it's really strange that in these three cases if I output
0 5
5 0
0 0
I will get a WA...., if I output the another answers I will get AC...
why?

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

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

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;
}

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

There are 2 (TWO) lines in the sample. First contains count of stones, second contains stones weights.

Your test should look like:
---
6
1 4 5 6 7 9
---

By the way some languages (C scanf/C++ iostream/Java scanners) allow reading from input without checking how data items are placed on input lines.
Here - http://acm.timus.ru/help.aspx?topic=csharp - input read in similar way via
      string[] input = Console.In.ReadToEnd().Split(
         new char[] {' ', '\t', '\n', '\r'},
         StringSplitOptions.RemoveEmptyEntries);

        EGGS=2, FLOORS=20
        (20 eggs, initial step = 7)
        e=20(20)
        7 14 17 18 19
        e=19(20)
        7 14 17 18 19 (+7, +3)
        ...(e=18..14 )
        e=13(20)
        7 14 8 9 10   11 12 13 [7 moves]
        (20 eggs, initial step = 7)

        (20 eggs, initial step = 6)
        e=5(20)
        6 1 2 3 4 5
        e=17(20)
        6 12 18 13 14 15 16 17 [8 moves]

        (20 eggs, initial step = 5)
        e=20(20)
        5 10 15 18 19 20
        e=17(20)
        5 10 15 18 16 17
        e=14(20)
        5 10 15 11 12 13 14

        (20 eggs, initial step = 4)
        4 8 12 16 20 17 18 ..
thanks! also what is the algorithm for this particular test case? thanks

Edited by author 10.11.2013 14:51

Edited by author 10.11.2013 14:51

Edited by author 10.11.2013 14:51

Fix output as task required - remove spaces after Yes and No, remove "cout << num;".

800
5
725 + 75 = 800
728 + 72 = 800
730 + 70 = 800
750 + 50 = 800
800 + 00 = 800
100168
8
90584 + 9584 = 100168
91034 + 9134 = 100168
91059 + 9109 = 100168
91062 + 9106 = 100168
91064 + 9104 = 100168
91084 + 9084 = 100168
95084 + 5084 = 100168
100084 + 00084 = 100168

Sorry, was wrong.

Edited by author 17.03.2016 14:29