My solution for Round #310 (Div 1) C and D (555C, 555D)
Difference between en10 and en11, changed 47 character(s)
[problem:555C]↵
==================↵

Initially there is only one single piece of chocolate. It is the problem's requirement that subsequent same coordinates should return 0 so we can use a set to store those coordinates. (For example, the sample two has two 10 1 so the second 10 1 should return 0.↵

Continuing the concept of pieces, observe that after one valid operation, the chocolate would be split into two (possibly zero area) pieces. The pieces will both have a straight top and left edges. We store the edges using pair<int, int> using a map with key = piece locations to efficiently locate the correct piece to compute / modify.↵

In each operation, the answer is the distance between the starting point to the edge. After that, for U operation, the new piece will have the same top edge and same left edge, but we modify the old piece's left edge = the x coordinate. For L operation, the new piece will have the same left edge but the top edge is the y coordinate. Add the new piece to map with key = x coordinate.↵

Complexity = $O(q\ lg\ n)$. My solution: [submission:11813356]↵

For example, in the second sample, you have $[1, 11)$ initially. The first operation 2 9 U splits the chocolate into $[1, 2)$ and $[3, 11)$. The second operation 10 1 U splits $[3, 11)$ into $[3, 10)$ and $[11, 11)$. The third operation 1 10 U splits $[1, 2)$ into $[1, 1)$ and $[2, 2)$. The fourth operation 8 3 L splits $[3, 10)$ into $[3, 8)$ and $[9, 10)$.  The sixth operation 6 5 L splits $[3, 8)$ into $[3, 6)$ and $[7, 8)$. In the image below, the edges are marked in magenta.↵

[problem:555D]↵
==================↵

The basic concept is to use binary search to find the peg that line will rotate about. If the peg found is the same as the current peg, output that peg. (except on the first try as illustrated on the image below (right example)).↵

Sometimes the line will keep rotating about two pegs that are close together. For example, $l = 1000000$ and $peg_1 = 1$ and $peg_2 = 2$. We can accelerate this: if we are working on the same pair again, remaining length %= the distance between those two pegs * 2 (do not change direction). If we do so, the remaining length will be at most half of the previous length after operation. This guarantees that we can find the solution in
lg l$\text{lg}\ n\ \text{lg}\ l$ time in each query.↵

Complexity = $O(q\ \text{lg}\ n\ \text{lg}\ l)$. My solution: [submission:11813021]↵

Note that the problem did not guarantee that the pegs are sorted. So you have to sort them.

#### History

Revisions Rev. Lang. By When Δ Comment
en11 microtony 2015-06-28 09:38:43 47 Tiny change: 'ution in $lg\ n\ \text' -> 'ution in$\text{lg}\ n\ \text'
en10 microtony 2015-06-28 06:35:32 0 (published)
en9 microtony 2015-06-28 06:34:57 30
en8 microtony 2015-06-28 06:34:02 2 Tiny change: '$peg_1 = 1 and peg_2 = 2$' -> '$peg_1 = 1$ and $peg_2 = 2$'
en7 microtony 2015-06-28 06:31:59 1027
en6 microtony 2015-06-28 06:17:06 96 Tiny change: '419da.png)' -> '419da.png)\n\n[problem:555C]\n=================='
en5 microtony 2015-06-28 06:14:25 61
en4 microtony 2015-06-28 06:13:25 56 Tiny change: 'orces.com/668842/555C2.png' -> 'orces.com/5649bc/555C2.png'
en3 microtony 2015-06-28 06:11:46 192
en2 microtony 2015-06-28 06:04:16 938
en1 microtony 2015-06-28 05:35:52 620 Initial revision (saved to drafts)