Where do you find the information that the Fun SRM is rated? The TC emails don't even mention about the mirror contest...

What do you calculate in the DP? I guess you find number of subsets of collinear points, but in a strange way.

Answer is . This correction make it AC in and .

It means that if before a step, the function is of this form, then after either applying the function g1 or g2, it will still be of this form.

As is common on Atcoder, this problem also features a very nice (maybe easy to some, but I couldn't figure during contest) if-and-only-if observation. Note that the problem is trivially equivalent to counting, for each convex set (defined in the statement), the number of subsets of the set of points lying inside or on it except the vertices themselves (2^n - S). As is to be expected, this is counted differently for the solution. It says that it is sufficient to count sets for which the convex hull has a positive area. Formally the problem requires us to count pairs (X, U) such that . But consider . From this we can uniquely determine X = points - in - convex - hull(S), U = S - X. This works as suppose we can add another element from U to X, then X contain a superfluous element, which by definition (no collinear points) are not allowed. On the other hand, (X, U) obviously uniquely determines , proving that S → (X, U) is a bijection, thus their cardinalities are the same.

Next, note that all such S are nothing but all sets with positive area of convex hull, each counted only once, as S obviously have positive area of convex hull, and each set with positive convex hull can be used to write such an S.

Now to count convex hulls with positive area, it is necessary to opposite-count, thats is count sets with 0 area, and that is trivial.

First, note that we don't really need to know how much sand there is in bulb B since it's just X minus the amount of sand in bulb A. Every time bulb A is on top, it loses 1 unit of sand each second, until it has 0 sand left. Similarly, when it is at the bottom, it gains 1 unit of sand each second, until it has X units of sand left.

Let f(x) denote the amount of sand bulb A will contain if it starts with x units of sand. We'll keep track of this function every time we flip the bulb.

The key is to note that the function f can always be defined by 4 integers (actually one of them can be computed from the other 3 but we'll keep all 4 for convenience), mn, mx, l, r. f(x) = mn if x < l, f(x) = mn + x - l if l ≤ x ≤ r and f(x) = mx if x > r.

Initially, f(x) = (0, X, 0, X).

Let's see how the function change when we flip the sandglass after v seconds. Suppose before we flip the sandglass, bulb A is losing sand. Thus, bulb A will lose v units of sand in total during this period. Suppose previously f(x) = (mn, mx, l, r).

If v ≤ mn, then the new function is g(x) = (mn - v, mx - v, l, r), as it's just the entire function shifted down by v units.

If v > mn, then the values l, r might change, since the function goes below 0 after shifting down by v units and we need to make the front part become 0 again. You can check that in this case, the new function is g(x) = (0, max(mx - v, 0), min(l + v - mn, X), max(min(l + v - mn, X), r)).

If bulb A gains sand for v seconds, we can update the function in a similar manner.

Thus, we can update the function in O(1) for each time period.

Now, to answer each query (t, v), where t is the amount of time passed and v is the initial amount of sand in bulb A, let's binary search to find the largest time y ≤ t where the sandglass is last flipped. Plug in v into the function at time y (which we precomputed in the beginning for all moments we flip the sandglass) to get the amount of sand in bulb A after y seconds in O(1). Then, depending on the parity of the number of flips performed, we add or subtract the amount of sand in bulb A by t - y (taking max with 0 or min with X if needed) to get the final amount of sand in bulb A. Thus, each query can be answered in time.