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;
}
Do not use "new" operation. You can prepare a pool for the allocation of space.
I don't know ,how i can do this. Can you show ?
Also, consider using 32-bit integer handles instead of pointers. On 64-bit systems, this will cut your memory usage in half.
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.