-
-
Notifications
You must be signed in to change notification settings - Fork 300
/
981.cpp
93 lines (86 loc) · 2.86 KB
/
981.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
__________________________________________________________________________________________________
sample 308 ms submission
static int _ = []() {
ios_base::sync_with_stdio(0);
cin.tie(0);
return 0;
} ();
class TimeMap {
struct info {
int t;
string v;
info(int t, string &v): t(t), v(move(v)) {}
};
unordered_map<string, vector<info>> m;
public:
/** Initialize your data structure here. */
TimeMap() {
}
void set(string key, string value, int timestamp) {
m[key].emplace_back(timestamp, value);
}
string get(const string &key, int timestamp) {
auto it = m.find(key);
if (it==m.end() || it->second[0].t>timestamp) return "";
auto &v = it->second;
if (v.back().t<=timestamp) return v.back().v;
int l=0, r=v.size()-2;
while (1) {
int mid=(l+r)/2;
if (v[mid].t<=timestamp && timestamp<v[mid+1].t) return v[mid].v;
if (v[mid].t>timestamp) r=mid-1; else l=mid+1;
}
}
};
/**
* Your TimeMap object will be instantiated and called as such:
* TimeMap* obj = new TimeMap();
* obj->set(key,value,timestamp);
* string param_2 = obj->get(key,timestamp);
*/
__________________________________________________________________________________________________
sample 128916 kb submission
class TimeMap {
public:
/** Initialize your data structure here. */
TimeMap() {
return;
}
void set(string key, string value, int timestamp) {
if (tmap.find(key) == tmap.end()) {
tmap[key] = vector<pair<int, string> >(1, make_pair(timestamp, value));
} else if (value != tmap[key].back().second) {
tmap[key].push_back(make_pair(timestamp, value));
}
}
string get(string key, int timestamp) {
if (tmap.find(key) == tmap.end()) {
return "";
} else if (timestamp < tmap[key][0].first) {
return "";
} else if (timestamp >= tmap[key].back().first) {
return tmap[key].back().second;
} else {
int head = 0, tail = tmap[key].size() - 1;
while (head < tail) {
int tmp = (head + tail) / 2;
if (timestamp < tmap[key][tmp].first) {
head = tmp;
} else if (timestamp > tmap[key][tmp].first) {
tail = tmp;
} else
return tmap[key][tmp].second;
}
return tmap[key][head].second;
}
}
private:
unordered_map<string, vector<pair<int, string>>> tmap;
};
/**
* Your TimeMap object will be instantiated and called as such:
* TimeMap* obj = new TimeMap();
* obj->set(key,value,timestamp);
* string param_2 = obj->get(key,timestamp);
*/
__________________________________________________________________________________________________