Thanks, you made my day

I used python to solve the problem But I'm stuck in the case when the leading zeroes come. Can someone help me with that ?.

My submission is 55661488

the problem is that you have here various color so you have to go through a series of corner cases and handle a lot of if-else to do stack implementation. I don't know but it should be really complex if it exists.

I'll try — imagine a rectangle with width M and infinite height. Every year you color one cell of this rectangle, going bottom to top and left to right. The column you color corresponds to the city in which the olympiad happens — so in year T you will color city (T mod M) by this process.

The problem is that some N cells are already colored. The coloring proceeds normally, except you skip colored cells. So for a given T, all you want to find is the number of cells you skip. This can be done by sorting these cells in the order in which they would be filled normally, and then binary search.

did u get how is this code working ?

Think in terms of time. S time at which last merging occurred and query time is current time.

core idea is to find valid cut in O(x) (seems that there's a typo in editorial?) by sorting in 4 directions (left to right, right to left, top to bottom and bottom to top) and go through these arrays simultaneously until you find a valid cut or you have gone through all those arrays.

Years can be upto 10**18. Try changing int to long long.

i dont think your code would promise count<=1e6 so that "result[x-n]" might overflow. you could try your code with the following test case:

500000 500000 1
1 1 1 ... 1
100000007

First, find the number of same coloured cells to the right and bottom of each cell(plain dp). Now for each cell, check the row number of next colour and row number of next next colour along the same column. Find the maximum width of the rectangle by performing range query(segment tree).

take a dp matrix to know the number of same coloured cells from top to bottom. then, try to find a series of cases to do counting. here I am giving the code(try to understand the cases from line 39). here is the code. https://codeforces.net/contest/1181/submission/55669150

We understood, that the next olympiad will take place in the k-th city(we will assume, that cities which can organize the olympiad sorted by their number). now we will talk about segment tree. Vertex in this segment tree will responsible for how many cities form l to r can organize the olympiad.Consider you are in the vertex v, and the olympiad will take place in either of cities from 2 * v, or 2 * v + 1.If the value of the vertex 2 * v larger than k, it means that there is no point in looking for k-th city in vertex 2 * v + 1.In other case we will check vertex 2 * v + 1, instead of vertex 2 * v.

I have an idea that you can consider the effect of each cell as the lower right corner on the answer.my submission

see the comment of cerberus97 above

10001

the same problem. Did u find a solution?

After several long long hours of reading code of hundred of people, I finally have figured it out. You can read the easiest-to-understand-code-for-me I have found here .

I think you should try as hard as possible to understand it (draw the segment tree, run that code with some test and try to understand it) as you will learn a lot when you yourself can figure it our on your own.

But if you still struggle with it, just message me I will explain it for you.

Something like this: