fixed. thanks!

How to solve D with BONUS: Solve for HW ≤ 200!?

Not sure, but I think it is wrong because you count the ways you can lay the tiles, but asked is the number of different outcomes.

here, https://atcoder.jp/contests/abc196/submissions/21107210

D can be solved in O((3^(HW))*HW).

Yeah it is !!

I just wrote a plain brute force recursive solution and it passed in 6ms.

Its complexity is O(3^(H.W)).

I just wrote a most brute-force brute force which I don't know the complexity, and it passed.

I used recursion, numbered all cells and placed dominoes on them in strictly increasing order. This works very fast.

solve(A, Map[][], Last):
	if A=0:
		res++
	else while:
		find_cell_at_which_we_can_place_dominoe_2x1_starting_from(Last)
		place_dominoe()
		solve(A+1, NewMap[], NewLast)
		remove_dominoe()

i used this blog https://codeforces.net/blog/entry/59386

Try to plot the graphs of some compositions, you can then prove that the final graph would either be a constant or something like this:

Next you know the maximum and minimum values of $$$g(x)$$$(values at $$$10^{18}$$$ and $$$-10^{18}$$$), then find $$$a$$$ and $$$b$$$ using binary search and finally $$$m$$$ and $$$c$$$. Answer queries in $$$O(1)$$$.

We can notice a truth that if we sort the array by ascending, now assume we process an operation $$$t_i=2$$$($$$t_i=3$$$ is the same), all the elements less than $$$a_i$$$ will become $$$a_i$$$. So we can take all the elements less than $$$a_i$$$ from some data structure and union them with a new element, which's value is $$$a_i$$$. After that, we can put the new element into the data structure.

So we can solve this problem off-line. We just need a set to restore all values and a data structure to union some elements. Because every element will be put into and taken out the set at most once, the total time complexity is $$$O(nlogn)$$$.

See code for more details.

My solution is similar to editorial, so I might explain the intuition. First observe that max(a + b, a + c) = a + max(b ,c). same holds for min Now we can convert each query to the form t[i] = 2 or t[i] = 3. Observe these queries are simple map of some range to some other so we start with L= -inf and R = inf and get the final mapping, add take care of extra addend. My submission https://atcoder.jp/contests/abc196/submissions/21104621
Complexity for each query in online mode is O(1) .

check this solution:sol
By storing "max value" and "second max value" we can handle the query that need to min($$$ a_i $$$,x) for every one $$$a_i$$$ and same for max($$$ a_i $$$,x) query. It's called "势能线段树“ in Chinese but I don't know what's in English :/.

I did a similar thing too, by storing range sum, max, and min — link

This is mine: https://atcoder.jp/contests/abc196/submissions/21106507

Your approach will definitely timeout. N is very big and your solution is O(n). An O(|n|) solution passes. Where |n| is the length of the number (or string) n. Pick the largest digit that matches the condition(s) and is not greater than n. The answer is the first half.

If m = n/2, the brute force complexity is n^2/4

Here rotations and reflections are considered different arrangements and we should count them separately, so basic recursion will work.