#include<iostream>
#include<chrono>
#include<cstring>
#include<algorithm>
#include<queue>
#include<unordered_map>
#include<climits>
using namespace std;

class LRUCache {
public:
    struct Node{
        int key;
        int val;
        long timestamp;
        Node *left,*right;

        Node(int _key,int _val):key(_key),val(_val),left(NULL),right(NULL){};
        Node(int _key,int _val,int _ts):key(_key),val(_val),timestamp(_ts),left(NULL),right(NULL){};
    }*L,*R;

    struct Comparator{
        unordered_map<int,Node*>* map;
        Comparator(unordered_map<int,Node*>* m):map(m){}
        bool operator()(int a,int b)const{
            return (*map)[a]->timestamp>(*map)[b]->timestamp;
        }
    };

    unordered_map<int,Node*> hash;
    priority_queue<int,vector<int>,Comparator> timeQueue;
    priority_queue<int,vector<int>,Comparator> tempQueue;

    int n;

    void remove(Node* p){
        p->left->right=p->right;
        p->right->left=p->left;
    }

    void insert(Node* p){
        p->left=L;
        p->right=L->right;
        L->right->left=p;
        L->right=p;
    }

    void deleteOverdueNode(){
        auto now=std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now().time_since_epoch()).count();
        while(!timeQueue.empty()&&now>hash[timeQueue.top()]->timestamp){
            int key=hash[timeQueue.top()]->key;
            timeQueue.pop();
            auto p=hash[key];
            remove(p);
            hash.erase(key);
        }
    }

    LRUCache(int capacity):timeQueue(Comparator{&hash}),tempQueue(Comparator{&hash}) {
        n=capacity;
        L=new Node(-1,-1),R=new Node(-1,-1);
        L->right=R,R->left=L;

    }

    int get(int key) {
        deleteOverdueNode();
        if(hash.count(key)){
            auto p=hash[key];
            remove(p);
            insert(p);
            return p->val;
        }
        return -1;
    }

    void put(int key, int value, long timestamp=INT_MAX) {
        if(!hash.count(key)){
            //auto p=hash(key);
            if(hash.size()==n){
                auto node=R->left;
                remove(node);
                hash.erase(node->key);
                while(!timeQueue.empty()){
                    int k=timeQueue.top();
                    timeQueue.pop();
                    if(k!=node->key){
                        tempQueue.push(k);
                    }
                }
                swap(timeQueue,tempQueue);
            }
            auto node=new Node(key,value,timestamp);
            hash[key]=node;
            insert(node);
            timeQueue.push(key);
        }else{
            auto p=hash[key];
            p->val=value;
            p->timestamp=timestamp;
            remove(p);
            insert(p);
            while(!timeQueue.empty()){
                int k=timeQueue.top();
                tempQueue.push(k);
                timeQueue.pop();
            }
            swap(timeQueue,tempQueue);
        }
    }
};

int main(){
    cout<<"hello world"<<endl;
    return 0;
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */