# 92 ms solution with Cartesian tree

• ``````#include <iostream>
#include <cstdio>

using namespace std;

struct node_t{
int m_key;
int m_value;
int m_priority;
node_t* m_left;
node_t* m_right;
node_t() : m_key(0), m_value(0), m_priority(0), m_left(NULL), m_right(NULL) {}
void show(){
printf("key:%d, value:%d, p:%d\n", m_key, m_value, m_priority);
}
};

void show_tree(node_t *t, int indent){
if(!t) return;
for(int i = 0; i < indent; i++) printf(" ");
t->show();
show_tree(t->m_left, indent + 4);
show_tree(t->m_right, indent + 4);
}

void cut_tree(node_t *t, int v, node_t* &l, node_t* &r) {
node_t *pTree;

l = r = NULL;
if(!t) return;

if(v < t->m_key){
cut_tree(t->m_left, v, l, r);
pTree = t;
pTree->m_left = r;
r = pTree;
}else{
cut_tree(t->m_right, v, l, r);
pTree = t;
pTree->m_right = l;
l = pTree;
}
}

void cat_tree(node_t* &t, node_t* &l, node_t* &r){
if(!l) t = r;
else if(!r) t = l;
else if(l->m_priority < r->m_priority){
cat_tree(t, l->m_right, r);
l->m_right = t;
t = l;
}else{
cat_tree(t, l, r->m_left);
r->m_left = t;
t = r;
}
}

void insert_tree(node_t* &t, node_t* n){
node_t *l, *r;
if(!n) return;
n->m_left = n->m_right = NULL;
if(!t){
t = n;
return;
}
if(n->m_priority < t->m_priority){
cut_tree(t, n->m_key, l, r);
n->m_left = l;
n->m_right = r;
t = n;
}else if(n->m_key < t->m_key){
insert_tree(t->m_left, n);
}else{
insert_tree(t->m_right, n);
}
}

int search_tree(node_t *t, int key){
if(!t) return -1;
if(t->m_key == key) return t->m_value;
if(key < t->m_key) return search_tree(t->m_left, key);
else return search_tree(t->m_right, key);
}

void extract_tree(node_t* &t, int key){
if(!t) return;
node_t *tree = NULL;
if(t->m_key == key){
cat_tree(tree, t->m_left, t->m_right);
t = tree;
}else if(key < t->m_key){
extract_tree(t->m_left, key);
}else{
extract_tree(t->m_right, key);
}
}

class LRUCache{
public:
int m_c;
int m_size;
node_t *m_lru;
int m_access;

LRUCache(int capacity) {
m_c = capacity;
m_lru = NULL;
m_access = 0;
m_size = 0;
}

int get(int key) {
int v;
v = search_tree(m_lru, key);
if(v != -1){
extract_tree(m_lru, key);
node_t *n = new node_t();
n->m_priority = m_access++;
n->m_key = key;
n->m_value = v;
insert_tree(m_lru, n);
}
return v;
}

void set(int key, int value) {
int v;
v = search_tree(m_lru, key);
if(v != -1){
extract_tree(m_lru, key);
m_size --;
}
while(m_size >= m_c){
extract_tree(m_lru, m_lru->m_key);
m_size --;
}
node_t *n = new node_t();
n->m_priority = m_access++;
n->m_key = key;
n->m_value = value;
insert_tree(m_lru, n);
m_size++;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.