class TimeMap {
private HashMap<String, List<Pair>> map;
public TimeMap() {
map = new HashMap<>();
}
public void set(String key, String value, int timestamp) {
if (!map.containsKey(key)) {
map.put(key, new ArrayList<>());
}
map.get(key).add(new Pair(value, timestamp));
}
public String get(String key, int timestamp) {
if (!map.containsKey(key)) {
return "";
}
var list = map.get(key);
int l = 0, r = list.size() - 1;
while (l < r) {
int mid = (l + r + 1) / 2;
if (list.get(mid).time <= timestamp) {
l = mid;
} else {
r = mid - 1;
}
}
return list.get(l).time <= timestamp ? list.get(l).value : "";
}
private class Pair {
String value;
int time;
public Pair(String value, int time) {
this.value = value;
this.time = time;
}
}
}