I know there are much simpler ways of solving this problem but segment trees were the first to come to my mind. Since I'm not so good with trees I wanted to give it a shot. Here's the basic logic.
- Make a segment tree separately for both the width and the height. Each node must store its max volume, and the maximum sized fragment it can hold. Also, the leftmost and the rightmost cut.
- X height Cut is denoted by the left edge of the (X+1)th unit length segment of the segment tree leaves. eg. cut at height 3 would be denoted by the 4th block's left edge.
- On cutting the glass, the info is updated on the larger segments as we move up. Ultimately the root holds the value of the largest fragment available.
- Multiply the largest of the height tree and width tree to get the size.
Note: — leftmost and rightmost are initialized to -1 since no nodes contain any cut in the beginning PS. If you read it please point out any mistakes. This was the accepted Solution
public class node {
int leftmost, rightmost, max;
int v = 1;
// v is the volume a segment occupies. Max is the maximum size of
// glass fragment we can get from it in the current condition
public node() {
leftmost = -1;
rightmost = -1;
max = 1;
}
}
public class SegmentTree {
node[] arr;
int k;
int n;
public SegmentTree(int n) {
this.n = n;// initializing the segment tree.
k = (int) (Math.log(n) / Math.log(2));
if (!((n & (n - 1)) == 0)) {
k++;
}
k = (int) Math.pow(2, k);
arr = new node[2 * k];
init(1);// max value and volume value's (max and v)
// initialization is done.
}
public void init(int p) {
if (p >= k) {// p>=k implies we reached the leaf node
arr[p] = new node();
if (p >= n + k)// implying that this node is beyond limits.
// Inaccessible so vol=0;
arr[p].v = arr[p].max = 0;
else
arr[p].v = arr[p].max = 1;
return;
}
init(2 * p);
init(2 * p + 1);
arr[p] = new node();
arr[p].v = arr[p].max = arr[2 * p].v + arr[2 * p + 1].v;
}
public int getLeftChild(int p) {
//gets the leftmost child of a vertex. Used to get the relative height
while (p < arr.length)
p *= 2;
return p / 2;
}
public void insert(int h) {
int p = k + h;//reach the appropriate leaf node.
arr[p].rightmost = h;
arr[p].leftmost = h;
p /= 2;
while (p != 0) {//Iteratively update the parents
int left = 2 * p;
int right = 2 * p + 1;
int start = getLeftChild(p);
start -= k;//make the start in terms of h
//3 cases arise:
//1. left child has no cut
//2. right child has no cut
//3. both childs have cuts
if (arr[left].rightmost == -1) {
arr[p].max = Math.max(
Math.max(arr[left].max, arr[right].max),
arr[right].leftmost - start);
} else if (arr[right].leftmost == -1) {
arr[p].max = Math.max(arr[p].v
- (arr[left].rightmost - start),
Math.max(arr[left].max, arr[right].max));
} else {
arr[p].max = Math.max(
Math.max(arr[left].max, arr[right].max),
arr[right].leftmost - arr[left].rightmost);
}
//reassign the leftmost and rightmost of the current node
arr[p].leftmost = arr[left].leftmost;
arr[p].rightmost = arr[right].rightmost;
if (arr[p].leftmost == -1)
arr[p].leftmost = arr[right].leftmost;
if (arr[p].rightmost == -1)
arr[p].rightmost = arr[left].rightmost;
p /= 2;
}
}
}
public void Solve() {
int w = ni();
int h = ni();
int n = ni();
SegmentTree width = new SegmentTree(w);
SegmentTree height = new SegmentTree(h);
for (int i = 0; i < n; i++) {
String line[] = l().split(" ");
int p = Integer.parseInt(line[1]);
if (line[0].equals("H")) {
height.insert(p);
} else {
width.insert(p);
}
long x1 = height.arr[1].max;
long x2 = width.arr[1].max;
System.out.println(x1 * x2);
}
}
