The Ray will always move with a vector (1,1) or (-1,1) or (1,-1) or (-1,-1) because it always change its direction 90° and in a straight line. For every one of this lines, witch are all parallels to the diagonals, if you extend them to the infinite they only cut once the x axis. In fact, they cut the x axis in (x+y) if the vector is (1,1) or (-1,-1) and in (x-y) if it is (1,-1) or (-1,1). You can then calculate for every sensor this number for the both line that pass throughout it. You make then lists of sensors for each possible sum and difference of coordinates.

You then simulate the ray, going from wall to wall in O(1), and checking and updating all the sensor that are in both lines that pass trough every point in the wall you touch.

It's then O(N) with N being the number of sensors.

Pretty cool! Could you explain for nubbie please)?

I doubt that O(1) solution exist, but here I describe idea for O(log(n+m)) solution: http://codeforces.me/blog/entry/47598#comment-319789

21347465 is my Accepted code using Chinese Remainder Theorem. I think it is O(1) though not completely sure.
21286454 is definitely O(1) query time, written by eatmore

I just can't understand why I get downvote. Or that we shouldn't point out typos?

21398786 didnt work for me

Fix vector u in the basis which has i-th bit. Not depending on vector v from first 2^{r-1} vector, one of v and v xor u will have 1 and other one will not

it is important to observe that if a letter L is needed then all the occurrences of the letter from 1..L-1 will be included in the lexicographically smallest string. Now the main problem is to find the least number of occurrence of the letter L.

The initial problem is to find the max smallest letter L within which we will be able to visit all the intervals. To do this, we will iterate through all the intervals for each of the letters. In each iteration we will check whether the current letter indexes can fill any intervals and mark them. While doing this we will have to make sure that we always take the right most position and if we can use that position in other interval then we have to use it as it will solve our main goal of taking the least number of occurrence of the current letter. See the below test cases for clarification.

test case: 3 aaaaaaaaa ans : aaa

3 ababab ans : aa

I did. It became extremely complicated though.

21310505

I did too. But it was only used for looking up "rightmost minimum character in an interval". I wish to note than it can also be done with RMQ: O(n log n) preprocessing and O(1) queries, but I find segment trees less error-prone and easier to code, so that's what I used.

Code: http://codeforces.me/contest/724/submission/21289565

The mistake you made wasn't ignoring the "zero" cycles but "int mr = min(sz, 60)"

notice that mr may be larger than sz

what if cyc = {1, 4} ?

You will get mr = 2, base = 1, r = 1 but it should be that mr > 2, base = 5, r = 2.

So just change it to "int mr = 60;" and everything will be right.

They meant c, maximum amount of goods for a single transportation. So they cut all edges to j cities, which are currently in set A.

You consider two cases. If you assign the ith vertex to set A, the capacity increases by si. Instead, if you assign ith vertex to set B, capacity of cut increases by pi+j*m. The j*m value comes from the j vertices in set A such that there is edge from those to ith vertex.

"via other already seen cities that don't produce, but can be used to transfer goods through them"

Can you please explain this a bit more?

Eh, could you please explain your solution ?

I am only able to solve the problem with the complex O(n²)

Thx.

Cut edges are saturated in max flow.