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
| map<int, int>::iterator front(map<int, int>& mp, int f) {
if(mp.empty()) return mp.insert(make_pair(f,f)).first;
auto it = mp.upper_bound(f);
if(it == begin(mp)) {
return mp.insert(make_pair(f,f)).first;
}
--it;
if(it->second + 1 >= f) return it;
return mp.insert(make_pair(f,f)).first;
}
void merge(map<int, int>& mp, int f, int e) {
auto it = front(mp, f);
it->second = max(it->second, e);
while(next(it) != end(mp) and next(it)->first <= it->second + 1) {
it->second = max(it->second, next(it)->second);
mp.erase(next(it));
}
}
int query(map<int, int>& mp) {
int res = 0;
for(auto& [f, e] : mp)
res += e - f + 1;
return res;
}
long long gridlandMetro(long long n, long long m, int k, vector<vector<int>> track) {
long long res = n * m;
sort(begin(track), end(track));
int l = 0, r = 0;
while(r < k) {
map<int, int> interval;
while(r < k and track[r][0] == track[l][0]) {
merge(interval, track[r][1], track[r][2]);
r++;
}
res -= query(interval);
l = r;
}
return res;
}
|
