computerbox's blog

Help me with Cartesian Tree (treap) implementation
By computerbox, 6 years ago, translation, In English

Hi to everybody ! I am solving problem Next on e-olymp ( https://www.e-olymp.com/en/problems/686) and i have Memory limit verdict . I don't know ,how i can fix it.Please help me to fix .

Code
  • Vote: I like it
  • -15
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Do not use "new" operation. You can prepare a pool for the allocation of space.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    I don't know ,how i can do this. Can you show ?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Also, consider using 32-bit integer handles instead of pointers. On 64-bit systems, this will cut your memory usage in half.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      1.Create a container of max required size

      2.Use a stack to keep track of available indexes.

      // define the max required space
#define MAX_SIZE 600005

//create a container of max size
int array[MAX_SIZE];
stack available;

//store all available index in stack
void init()
{
    for (int i=0; i<MAX_SIZE; i++)
    available.push(i);
}

//get will give index of any available space and remove it from available
int get()
{
    int index=available.top();
    available.pop();
    return index;
}

//in order to delete, add it back to stack
void free(int index)
{
    available.push(index);
}

      This technique provides better speed while execution since dynamic allocation of memory is not done. The problem is the max required space must be known in advance.

      P.S. The answer is written using a phone, so there might be issues with indentation and others.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thanks forgotter, i will try to understand it. Do you see my insert function ? I think all problems in this function. I think ,i implemented it very bad.

        → Reply