Help me with Cartesian Tree (treap) implementation

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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

/*
ID: computerbox --> Huseyn Hajiyev
LANG: C++
TASK: target_mode_on
*/
#include <bits/stdc++.h>
#define FAST_READ ios_base::sync_with_stdio(0);
#define ll long long
#define COUT(n, a) cout<< fixed << setprecision(a) << n<<endl
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define MAXN 2000

using namespace std;



ll n;

struct treap
{
   ll key,priority;
   treap *leftt,*rightt;

};

typedef treap* decart;
decart Tree,L,R;
ll ans;


void split(decart root,decart &L,decart &R,ll key)
{
  if(root==nullptr)
  {
	R=L=nullptr;
	return ;
  }
  if(root->key < key)
  {
	split(root->rightt,root->rightt,R,key);
	L=root;
  }
  else
  {
	split(root->leftt,L,root->leftt,key);
	R=root;
  }
}

decart merge(decart leftt,decart rightt)
{
  if(leftt==nullptr)return rightt;
  else if(rightt==nullptr)return leftt;
  if(leftt->priority > rightt->priority)
  {
     leftt->rightt=merge(leftt->rightt,rightt);
     return leftt;
  }
  else
  {
	rightt->leftt=merge(rightt->leftt,leftt);
	return rightt;
  }
}

decart newNode(ll key)
{
  decart temp=new treap;
  temp->key=key;
  temp->priority=rand();
  temp->leftt=temp->rightt=nullptr;
  return temp;
}

void insert(decart &root,decart vertex)
{
  if(root==nullptr)
  {
	 root=newNode(vertex->key);
	 return ;
  }
  if(root->priority > vertex->priority)
  {
	 if(root->key > vertex->key)insert(root->leftt,vertex);
	 else insert(root->rightt,vertex);
  }
  split(root,vertex->leftt,vertex->rightt,vertex->key);
  root=vertex;

}

ll getmin(decart root)
{
  if(root==nullptr)return -1;
  if(root->leftt==nullptr)return root->key;
  return getmin(root->leftt);
}

void erase(decart &root,ll key)
{
   if(root->key==key)merge(root->leftt,root->rightt);
   else
   {
	 if(root->key >key)erase(root->leftt,key);
	 else erase(root->rightt,key);
   }
}

void query(ll x)
{
  split(Tree,L,R,x);
  ans=getmin(R);
  cout<<ans<<endl;
  Tree=merge(L,R);
}





int main(){
srand(time(NULL));
FAST_READ;
Tree=newNode(0LL);
cin>>n;
ll sig=0;
for(ll i=1;i<=n;i++)
{
  char x;
  ll y;
  cin>>x>>y;
  if(x=='+')
  {
	if(sig)y=(y+ans)%1000000000;
	decart nuj=newNode(y);
	insert(Tree,nuj);
	sig=0;
  }
  else
  {
	sig=1;
	query(y);
  }
}


return 0;
}

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

Comments (5)

Write comment?

LiM_256

5 years ago, # |

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

→ Reply

computerbox

5 years ago, # ^ |

-6

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

ivan100sic

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

forgotter

1.Create a container of max required size

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

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.

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.

computerbox's blog