I think that's because author is using very many redefinitions.

Please check the code of the solution. The solution will be more clear for you after that.

For the time being, W4ynebot wrote a solution in the announcement blog, you can read it.

Let's say we have this input data:

10 90
4 1

This means that at 2 PM there is an apple on the tree at height of 90 cm, and at 10 cm height sits the caterpillar. We know, that between 10 AM and 10 PM caterpillar goes higher 4 cm/hour. When it's 10 PM caterpillar goes to sleep and slips down 1 cm/hour, until it's 10 AM again. So we have the process:

2 PM => 10 PM - goes UP a cm/h
10 PM => 10 AM - goes DOWN b cm/h
10 AM => 10 PM - goes UP a cm/h
...
10 AM => 10 PM - goes UP && gets the apple (if he can)

In our case caterpillars movements are:

10 => 42 (10 + 8h * 4 cm/h) - climbing (day 0)
42 => 30 (42 - 12h * 1 cm/h) - sleeping
30 => 78 (30 + 12h * 4 cm/h) - climbing (day 1)
78 => 66 (78 - 12h * 1 cm/h) - sleeping
66 => 90 (66 + 6h * 4 cm/h) - climbing (day 2) && got the apple

In the middle of the 2-nd day the caterpillar is high enough to reach the apple, so the answer is 2.

You need to make a couple of observations:

• Since the ants bounce against each other, the relative order never changes.
• We can plot the movement of the ants by putting the position on the x-axis and time on the y-axis. Then a single ant would be a line with slope  ± 1. What happens when two ants collide? They reverse, but since the lines have slope 1 and  - 1 respectively, you can continue drawing each line. Here's what I mean: image. The best way to look at this is that once two lines cross, the ants on each line 'switch' lines.
• Based on the above, we can then find all final positions, after all, each line will always contain some ant (not necessarily the initial ant), so the end positions are . You can sort these end positions. Since the relative order of the ants never changes, all you have to do is 'rotate' (as in, cyclical permutation) these final values and you're done. Now comes the hard part: how much will we have to shift the end positions?
• Fix a specific x position, say x = 1 / 2 (also, just to be clear, we have a cyclical x-axis with 0 and M joined together). Without loss of generality, label the first ant to the right of this position as ant 1. Now imagine a line going straight up from this position (recall that our x-axis was position, and our y-axis was time), and for all lines (or maybe paths would be a better term) calculate all y-positions at which this line intersects with our line at x = 1 / 2 (it's fine to round these y-values up to the nearest integer).
• Now move forward in time. The first ant to the right of x = 1 / 2 is some ant i (initially ant 1). What happens when a line crosses x = 1 / 2 from left to right? Now the first ant to the right is ant i - 1. From right to left? Ant i + 1. If you keep doing this, eventually you'll reach y = T and you'll know the number of the first ant to the right of x = 1 / 2. We already calculated all the final positions, and since (again) the relative order of the ants doesn't change, we can now trivially give each ant its final position.
• There is one small problem: T is very large, up to 10¹⁸. You can work around this by noting that since all lines have slope 1 or  - 1, after M timesteps they'll end up at the same x-position again. During these timesteps, the first ant to the right of x = 1 / 2 may have changed, but other than that, the situation is exactly the same as it was during t = 0. In other words, after M timesteps the number of the first ant to the right of x = 1 / 2 shifts with some k, so after T / M (integer division) it shifts (T / M) * k (in fact, k is rather easy to find: since all lines will cross our vertical line at x = 1 / 2 exactly once in any interval of M timesteps, k = a - b where a is the number of lines with slope 1, and b the number of lines with slope  - 1). After this, you will have to do another T%M timesteps, but since T%M < M$, every line crosses our vertical line exactly once, so you can just simulate this process (and by simulate, I mean checking the intersections passing our x = 1 / 2 line individually, not simulate all the ants).

The final complexity is .

Hopefully that made some sense, it should be enough to solve the problem. Here's my solution by the way: 16961705

EDIT: Here's an even shorter solution: 16970841. Very simple compared to the one in the editorial :)

Actually it can be solved without any simulation. Time still will be O(n ln n) due to sort.

1. Let sorted starting positions be p_1, ..., p_n.
2. As explained in author's solution, we can calculate final positions. Let them be q_1, ..., q_n (also sorted).
3. Let's calculate total (oriented) speed S of ants. It's some number in [-n, n]. After multiplying it by t we will have total (oriented) movement. There is some trick here: as t is very large, S * t will overflow 64-bit integers. But we can calculate it modulo n * m.
4. Let's calculate offset O between starting and final position (q_1 — p_1) + ... + (q_n — p_n). We can also calculate it modulo n * m.
5. Proposal: (S * t — O) is divisible by m. To prove it we need to reсall how q_i was calculated.
6. Let offset = (S * t — O) / m. Then ant that was on p_1 position on start will be on position q_(1+offset) on finish.

Another solution without simulation:

First, relabel the ants such that they are in increasing position with respect to their indices. We can reverse this relabelling at the end.

Next, imagine that each ant has a sign. When two ants pass each other they exchange signs. Consider the first ant (assume he is going right) — we know where it will eventually end up but we do not know what sign it will hold. Notice however that when the first ant meets another ant, the sign the first ant holds will increase by one. So we simply sum up how many times the first ant meets another ant.

Nsqrt(N) = 1e9 for max test.

erase works in O(log n), however, the following code runs in O(n):

int k = lower_bound(vv.begin(), vv.end(), v[i].first.second)-vv.begin();

thus complexity of your solution is O(n^2)

I was also hacked by this generator, but solution with unordered_map took ~7s and solution with map took ~0.38s on my machine.

Visual Studio STL is different from GCC STL (aka libstdc++). For example, the following code

int main() {
    std::cout << std::hash<int>()(100001) << std::endl;
}

prints 100001 for GNU G++/GNU G++11 and 1680716807 for Microsoft Visual C++ 2010. Also, unordered_set and unordered_map implementations themselves are probably different. So different STLs require different anti-hash tests. I guess that you are testing your program with Visual Studio while my anti-hash test is designed for gcc STL.

I believe this exact same problem exists in codechef's ex Easy section! And I did it the same way!

I use too and I got TLE ;/

http://www.codeforces.com/contest/652/submission/17020791 using Mo's

Really brilliant idea to add edge from a-b to make they are in same EBCC.

btw, if you can find EBCC correctly for multigraph, then only needed work is for any artifacts (u, v) check u.bcc == a.bcc and v.bcc == a.bcc.

Here is my code: click

In the code, used 'metParent' variable to handle multigraph(so if u — v have multiple edges, then do not classify as bridge)

In a sorted array work this rules:

v[i] <= v[j] if i < j
v[i] >= v[j] if i > j

So you sort the array, and then build a new one using pair of pointers (1, n) or (1, mid) making one of this sequences:

1, n, 2, n-1, 3, n-2 ...
1, mid, 2, mid+1, 3, mid+2 ...

The first one is simpler to implement, considering the case where n is odd

Done.

Thanks. Fixed.

The total size of all z[i] is O(m). I've fixed the complexity from O(n) to O(n + m).

Good day to you,

let's say you have an array (later Fenwinck → complexity) and for every END of segment, you add 1 to the value (I mean => if you have segment [1,5], then you do Array[5]++)

PS: A necessary here is to make the values lesser (but preserve their order). So from [1,10000000],[3,50000], you would do [1,4][2,3] (otherwise you would not have enough memory for it)

Now let us sort the array of segments by their beginning.

Here, for every segment you do following operation:

I) Sum all values of all elements of array, from 0 to END

II) Substract END of this segment from array (so for [1,5] you would do Array[5]--)

Now see, what happened to all segments. The sum of values is the number of ends, which end earlier, than END of current segment. How can we be sure that we didn't include any extra segment? Well it is thanks to (II). Here we already substracted values of ALL segments, which begin earlier, then our current segment (so we are considering only points which begin later and we are searching for those, whose END is earlier, than current END).

Here you see, that the complexity is O(N^2). It is time to use Fenwick. It has exact property we want! Add/Substract a value of any one element (in logarithmic time) + get the sum of 0→END also in logarithmic time!

If the explanation was confusing, or not enough, do not hesitate and ask for additional questions :)

Good Luck man! ^_^

Try this:

1. Consider a plane (L, R). Each segment is a point (L[i], R[i]) on this plane. This is only for better understanding.
2. If segment (a, b) is inside segment (x, y), x < a < b < y, it means that point (a, b) is to the right and to the bottom of (x, y).
3. The problem is reduced to very standard problem: for every point on the plane count the number of points to the right and to the bottom of it.
4. This is usually solved by sorting points by one coordinate and maintaining a fenwick tree by the other coordinate.
5. Of course, first you need to compress coordinates, so all of them are in [0, 2*n-1].
6. Iterate over points sorted by R, when you meet point (a, b), increase tree[a] and then count the sum tree[a+1] + ... + tree[2*n-1]. Here, tree[x] is 1 if we have seen the point with first coordinate equal to x, and 0 otherwise.
7. This sum contains the number of points that have greater first coordinate (because you start summing from a+1) and less second coordinate (because points are sorted by R, so only points to the bottom of line y=b are summed).

My solution is available in my last submits.

It's true, but it's not that easy to be proved. Every biconnected graph can be constructed as follows: first we have a loop, and each time we add a path on it. We choose a loop that contains an artifact edge E, then we can construct a path passing the edge E, by moving vertex A and vertex B to older paths or loop in the structure above.

Yes. Let (u,v) be the artifact edge. Suppose for every path p1 from A to u and p2 from B to v inside the component p1 and p2 have common edges. You can see that there exists a certain edge e* in the component for which every such pair of paths p1' and p2' pass through, otherwise you can construct disjoint paths. This edge e* separates the biconnected component in two which leads to a contradiction.