Оптимизация LRU-буфера

Средняя

В ядре высоконагруженного сервиса разрабатывается модуль LRU-кэширования (Least Recently Used) фиксированной емкости $C$ . Кэш хранит пары $(key, value)$ и обрабатывает поток команд:

PUT key value — записать значение value по ключу key. Если ключ уже существует, обновить его значение. Если емкость

C

исчерпана, предварительно удалить элемент, к которому обращались дольше всего (LRU).

GET key — запросить значение по ключу key. Если ключ присутствует в кэше, вернуть его значение и пометить ключ как самый свежий. Если ключ отсутствует, вернуть -1.

Входные данные

В первой строке задано целое число

C

(

1 \le C \le 10^4

) — максимальная емкость кэша.

В последующих строках содержатся операции в формате PUT key value или GET key (

1 \le key, value \le 10^9

) до конца входных данных.

Выходные данные

Для каждой операции GET выведите возвращенное значение в отдельной строке.

Примеры

Пример 1

Входные данные:

text

2
PUT 1 1
PUT 2 2
GET 1
PUT 3 3
GET 2
PUT 4 4
GET 1
GET 3
GET 4

Выходные данные:

text

Оптимизация LRU-буфера

Средняя

PUT key value — записать значение value по ключу key. Если ключ уже существует, обновить его значение. Если емкость

C

исчерпана, предварительно удалить элемент, к которому обращались дольше всего (LRU).

Входные данные

В первой строке задано целое число

C

(

1 \le C \le 10^4

) — максимальная емкость кэша.

В последующих строках содержатся операции в формате PUT key value или GET key (

1 \le key, value \le 10^9

) до конца входных данных.

Выходные данные

Для каждой операции GET выведите возвращенное значение в отдельной строке.

Примеры

Пример 1

Входные данные:

text

2
PUT 1 1
PUT 2 2
GET 1
PUT 3 3
GET 2
PUT 4 4
GET 1
GET 3
GET 4

Выходные данные:

text

Код

Загрузка редактора...