← 返回 meta 的题目列表Timed Cache / Expiring Key-Value Cache
类型：online_judge
Problem: Timed Cache / Expiring Key-Value Cache
Design and implement a key-value cache where each key has a time-to-live, or TTL. Once the current timestamp reaches or exceeds a key's expiration time, that key should be treated as non-existent.
You are given a sequence of operations. The timestamps are provided in non-decreasing order.
Operations
The input contains Q operations. Each operation has one of the following formats:
SET t key value ttl
At timestamp t, store key -> value with expiration time t + ttl.
If key already exists, overwrite the old value and reset its expiration time.
This operation produces no output.
GET t key
At timestamp t, query key.
If key exists and has not expired, print its value.
Otherwise, print -1.
COUNT t
At timestamp t, print the number of non-expired keys currently in the cache.
Expiration Rule
If a key has expiration time expire_time, then:
it is valid when t < expire_time;
it is expired when t >= expire_time.
For example, after SET 0 a 10 5, key a is valid during [0, 5) and is expired at timestamp 5.
Input Format
Q
operation_1
operation_2
...
operation_Q
Output Format
Print one line for each GET and COUNT operation.
Constraints
1 <= Q <= 2 * 10^5
0 <= t <= 10^9
Timestamps are non-decreasing
1 <= ttl <= 10^9
key and value are strings without spaces
Example
Input:
7
SET 0 a 10 5
GET 3 a
GET 5 a
COUNT 5
SET 6 a 20 2
GET 7 a
GET 8 a
Output:
10
-1
0
20
-1
Example
Input
7
SET 0 a 10 5
GET 3 a
GET 5 a
COUNT 5
SET 6 a 20 2
GET 7 a
GET 8 a
Output
10
-1
0
20
-1