-
Notifications
You must be signed in to change notification settings - Fork 0
/
segment_manager.cpp
49 lines (45 loc) · 1.42 KB
/
segment_manager.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
class SegmentManager {
private:
int united_length_ = 0;
set<pair<int, int>> segments_rl_;
public:
int AddSegment(int l, int r) {
int border_intersection = 0;
for (auto iter = segments_rl_.lower_bound({ l, -1 }); iter != segments_rl_.end();
iter = segments_rl_.lower_bound({ l, -1 })) {
int other_l = (*iter).second, other_r = (*iter).first;
if (other_l < l) { // other_l...l
if (r < other_r) { // other_l...l...r...other_r
return border_intersection;
} else { // other_l...l...other_r...r
++border_intersection;
united_length_ -= other_r - other_l;
l = other_l;
}
} else { // l...other_l
if (other_l <= r) { // l...other_l...r
++border_intersection;
if (other_r <= r) { // l...other_l...other_r...r
++border_intersection;
united_length_ -= other_r - other_l;
} else { // l...other_l...r...other_r
united_length_ -= other_r - other_l;
r = other_r;
}
} else { // l...r...other_l...other_r
break;
}
}
segments_rl_.erase(iter);
}
segments_rl_.insert({ r, l });
united_length_ += r - l;
return border_intersection;
}
constexpr int GetUnitedLength() const { return united_length_; }
inline bool HasPoint(int point) const {
auto iter = segments_rl_.lower_bound({ point, -1 });
return (iter != segments_rl_.end() && (*iter).second <= point);
}
set<pair<int, int>>& GetSegmentsRL() const { return segments_rl_; }
};