task is here

Look up the solution for UVa 11402 Ahoy Pirates. That's what worked for me...

http://nminhtu94.blogspot.com/2012/12/uva-11402-ahoy-pirates.html

http://ajmarin.alwaysdata.net/codes/problems/1274/

http://lbv-pc.blogspot.com/2012/10/ahoy-pirates_24.html etc

EDIT: Not sure if you were looking for a detailed solution for the problem. If you did, I feel like after understanding the technique behind Ahoy, Pirates, you'll be able to figure out the solution for 'wall' yourself.

It's a rather complicated tree problem. At each node you need two values: down and up (the height when you call type 2 operation and type 1 operation, respectively).

• Set up the tree by making up = 0 and down = INF for every node.
• When you update the tree, combine every node along the path with its children. Let d_p and u_p be the values of the parent and d_c and u_c the values of the child. Then you combine them by doing the following four operations: 1) d_c = min(d_c, d_p), 2) d_c = max(d_c, u_p), 3) u_c = max(u_c, u_p), 4) u_c = min(u_c, d_p). After this, set d_p = INF and u_p = 0. By resetting the nodes along the path, you make sure that whatever operation is present on the parent comes after the operations on its children, and the reasoning for those four operations to combine them is as follows: 1) If you lower to height h on the child and to height h' on the parent after that, only min(h, h') will take effect. 2) If you decrease to height h on the child and then increase to height h' on the parent, with h' > h, then the first operation will lose effect. 3) If you increase to height h on the child and then increase to height h' on the parent, only max(h, h') will take effect. 4) If you increase to height h on the child and then decrease to height h' on the parent, with h' < h, then the first operation will lose effect.
• When you reach the node you need to update, if you need to increase to height h, you do down = max(down, h) and up = max(up, h). If, on the other hand, you're decreasing to height h, you do down = min(down, h) and up = min(up, h).
• After all the queries, you walk the tree from root to leaves and you combine every node with their children, as explained earlier (you don't do it for the leaves, obviously).
• Finally, you output min(down, up) for all the leaves of the tree.

Perhaps the code will be clearer than the explanation. Here --> C++ code