-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathP_732.java
More file actions
106 lines (88 loc) · 2.86 KB
/
Copy pathP_732.java
File metadata and controls
106 lines (88 loc) · 2.86 KB
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
94
95
96
97
98
99
100
101
102
103
104
105
106
package leetcode.hard;
import java.util.TreeMap;
@SuppressWarnings({ "unused", "InnerClassMayBeStatic", "PublicConstructorInNonPublicClass" })
public class P_732 {
class MyCalendarThreeTM {
TreeMap<Integer, Integer> tm;
MyCalendarThreeTM() {
tm = new TreeMap<>();
}
public int book(int start, int end) {
tm.merge(start, 1, Integer::sum);
tm.merge(end, -1, Integer::sum);
int active = 0;
int sum = 0;
for (int d : tm.values()) {
active = Math.max(active, sum);
sum += d;
}
return active;
}
}
class MyCalendarThree {
private class SegTree {
int leftMost, rightMost;
SegTree left, right;
long add;
long max;
SegTree(int leftMost, int rightMost) {
this.leftMost = leftMost;
this.rightMost = rightMost;
}
private void createChildren() {
if (left == null || right == null) {
final int mid = leftMost + rightMost >>> 1;
left = new SegTree(leftMost, mid);
right = new SegTree(mid + 1, rightMost);
}
}
private void recalc() {
max = Math.max(apply(left), apply(right));
}
private void propagate() {
createChildren();
left.compose(add);
right.compose(add);
add = 0;
}
private void compose(long add) {
this.add += add;
}
private long apply(SegTree st) {
return st.max + st.add;
}
private long query(int l, int r) {
if (l > rightMost || r < leftMost) {
return (long) -1e18;
}
if (l <= leftMost && rightMost <= r) {
return apply(this);
}
propagate();
recalc();
return Math.max(left.query(l, r), right.query(l, r));
}
private void update(int l, int r, long add) {
if (l > rightMost || r < leftMost) {
return;
}
if (l <= leftMost && rightMost <= r) {
compose(add);
return;
}
propagate();
left.update(l, r, add);
right.update(l, r, add);
recalc();
}
}
private final SegTree st;
public MyCalendarThree() {
st = new SegTree(0, (int) 1e9);
}
public int book(int start, int end) {
st.update(start, end - 1, 1);
return (int) st.max;
}
}
}