SPOJ: WILD – Wild West

This post is going to explain my solution for WILD – Wild West. My solution reach the first rank (when this thread is posted) when I use Fast IO. This solution is helped by Ahmad Zaky (user: azaky).

If we analyze the problem carefully, the problem is actually asking volume of cube with length of subtract with volume of the cuboids union. When I say union of cuboids, imagine multiple cuboids merge together (not the total volume sum of each cuboid). The problem is already abstracted to be “What is the volume of the merge cuboid?”. The constraint problem is , which means we need to solve is less than .

Imagine the problem 3 dimensional Cartesian system, skill A represents the X-axis, B represents the Y-axis and C represents the Z-axis.
It easy to state that, if a cuboid spans to (X-axis), (Y-axis) in (Z-axis), then definitely it will spans to (X-axis), (Y-axis) in (Z-axis). It means cuboid with higher c effects cuboid below.

If we try to look at each in (Z-axis) and we calculate the sum of space that is spanned by any cuboid (X,Y-axis), it is the volume of merge cuboid.
Now, we have abstracted the problem again. We need to calculate space that spanned by any cuboid for Z-axis in .

Assume there is 2 cuboid which spans to same some Z-axis value, let the first one is (, ) and another is (, ) (in terms of (X-axis, Y-axis)). if , the second cube will covers the first cube if and not if otherwise.

Let us a create a one dimensional array with length of which represents the x axis, and each element in the array represent the length of y axis that has been spanned (or vice versa x to y and y to x).
So, let us use the 1st testcase an example:

3 10
2 8 5
6 3 5
1 3 9

There are 3 cuboids, if we sort the Z-axis in smaller way, it might look something like this: (the second and third element order don’t matter)

1 3 9
2 8 5
6 3 5

So, we start with first. Since there are no cuboid that spans up to this Z-axis, all values in the array are 0.

0 0 0 0 0 0 0 0 0 0

Now, we reach to , the this is the first cuboid we meet. This updates the array to:

3 0 0 0 0 0 0 0 0 0

The volume of cuboid has spanned to value of 3. This happens until .
When we get to , the second element cause the array become:

8 8 0 0 0 0 0 0 0 0

The third cuboid updates the arrays to:

8 8 3 3 3 3 0 0 0 0

Note that the first and second value in the array doesn’t change because , it means there is a cuboid that spans y to 8 in x-axis of value 1 and 2 which covers a cuboid that spans less than that.
Now we calculate the value of the volume that spanned by the cuboids, this happens until . The total volume that spanned by union cuboids is . The answer is as expected.

The problem is now easy, try to have a data structure which has 2 following queries:
1. Do an update value for specified range and applied only when the previous value is less that that.
2. Can get the sum of total value

This can be solved with Segment Tree, but I am not going to explain that solution. Because I haven’t figured it out (though Zaky already has). My solution is pretty much the same as Subsequence Weighting solution. Using map<int, int>, you can do the update and sum in .

Here is my code: http://ideone.com/NUFn6z

Let me know if you need more explanation in the solution. 😀