The Sweep Line Algorithm is used here. It is a common algorithm.

The idea is to sweep a vertical "line" left to right and analyze the event points in chronological order. In this case, event points are left and right edges of each segment.

You may want to read this article for more.

Try input

3
1 1
2 3
1 2

and then

3
2 3
1 1
1 2

the result should stay the same, shouldn't it? :)

I cant even understand why we have to find exactly leftmost(

First, let's enumerate the columns of interest, because we believe that we may find a cell that has not been enlightened in them. Let's call this set of columns C = [c₁, c₂, ..., c_k + 1]

Notice that c₁ = 1, since it's the leftmost column in the grid and there's a chance there is at least one empty cell. As for the rest of the columns of interest, we cannot try every single other because the width of the grid can be up to 10⁹, so we should reason about which columns we should pick. Notice that if, when we are doing our binary search and we are evaluating if it's possible to enlighten the whole grid at a time t, the leftmost position an initially enlightened cell at (r, c) will be able to reach is (r, c - t). Therefore, column c - t - 1 may have one unenlightened cell. So we check for that column if that is the case. Let's do this for the remaining k initially enlightened cells (c₂, c₃, ..., c_k + 1), so we have a total of k + 1 columns to try for the leftmost one. The same way idea can be applied to the rightmost column, top and bottom rows.

How to check for a column c if it has one unenlightened cell? Let's iterate over every initialized enlightened cell (there are k of them). For each of them, at a time t, you want to know the range of cells from column c it is responsible for enlightening. Let's say that initialized enlightened cell is at (r', c'). The leftmost cell it's going to be able to enlighten is c' - t. If c' - t is at or left to c, it's obviously going to reach it, and what vertical range does it cover in this column? It's going to be [r' - t, r' + t], because as fire propagates in one direction, it's going to be propagating in the rest of the directions, so if it propagated t units to the left, every of those t columns covered will also cover t cells up and down. Store the range [l, r] this initialized enlightened cell spanned for column c in a list. Repeat for the rest of the k - 1 enlightened cells.

Now the only remaining step is, sort the list by l, in case of tie, by r. Calculate the total range it covers by keeping track of the last endpoint covered so as to avoid counting some segment more than once, and check if cellscovered < height_grid. If that is the case, there was at least one unenlightened cell in that column.

Maybe there is more clever solution, BUT YOU CAN find all lucky numbers til 999999. see my solution on profile. Its literally 6 foor loops from 0 to 9.

Complexity is 1 milion which passes easily, so why think clever if u can brute haha

What I did was the following: Assume WLOG that the sum of the first three digits is less than the sum of the last 3. Let the difference between the halves be d. You want to increase the sum of the first half and/or decrease the sum of the second half so that d = 0. If you have a digit, x, in the first half, you can use that the decrease d by (9 — x). Similarly, if you have a digit, y, in the second half, you can use that digit to decrease d by y. So, just put all (9-x)s and ys into a list, sort, and greedily subtract the largest values until d <= 0.

When a new speed limit sign comes, you also have to check if he is speeding. For example, if he goes with 50, at 60 speed limit, and 40 speed limit sign comes, you don't check it, though he is speeding.

What are those 3*k lines and columns formally?