Today

Unfortunately the timer version does not work (I just tested). I will update the thread if I can get some time to fix it before todays contest. Sorry.

Update: Timer also seems to be working.

There is another contest link format: https://atcoder.jp/contests/contest_id e.g. https://atcoder.jp/contests/agc009

So, beside link format like https://agc009.contest.atcoder.jp you may also consider to extend support for link format like https://atcoder.jp/contests/agc009

How to solve Yet Another Die Game?

for each 1 ≤ d ≤ m , you need to count number of points l_i, r_i such that l_i ≤ d, r_i ≥ d or l_i ≤ 2d, l_i > d, r_i ≥ 2d or l_i ≤ 3d, l_i > 2d, r_i ≥ 3d ... , so its just some rectangle sum queries which can be done offline with BIT.

Simply put, use a fenwick tree. I was crazy enough to use one that supported range updates, which was completely unnecessary :(.

The observation you have to make here is that you're going to iterate the positions where the train stops like the harmonic series, which will make your baseline complexity O(m log m).

The algorithm goes like this:
- Iterate the jump length (denote this as x) in decreasing order.
- While the longest segment we have in our heap is longer than x, pop it from the heap and update the fenwick tree accordingly.
- Iterate i, i+x, i+2x... and count number of segments containing the point using fenwick tree.

In implementation, do not use heap. Use sorted vector.

Complexity: (n log n + m log m)

All trains will visit about stations in total so you can run a simulation. Sadly, if you simply remember how many souvenirs can be purchased at a station, you may overcount whenever a segment is large enough to accomodate a train more than once.

To overcome this, notice that for a train of type d you will always visit a segment whose length is  ≥ d so these segments can be counted towards the answer and thrown away. The smaller segments will be visited at most once and can be handled with a segment tree in the above simulation.

In the increasing order of d, add segments that are no longer "long enough" to the segment tree and simulate the train d.

Example solution: http://arc068.contest.atcoder.jp/submissions/1083406

There is also a different solution in O(n*sqrt(m)). Let S=sqrt(m) and for each souvenir interval I, do the following:

For each 1<=i<=S, check whether the i-th train stops in I — if yes, increment that train's counter. For each S<=i<=m, the i-th train will make at most S stops in total. For each k, the set of trains that visit I on their k-th stop is either empty or some interval [a,b] with 1<=a<=b<=m. Iterate over 1<=k<=S and increment everything in [a,b] using a prefix sum array — except everything that you already incremented for some other k.

Implementation: http://arc068.contest.atcoder.jp/submissions/1085135

Let the number of i in a[i] -> c[i].
Let sum = min(c[0] - 1, 0) + min(c[1] - 1, 0) + ... + min(c[100000] - 1, 0).
The answer is n - floor(sum / 2) * 2.

Get the number of cards that you have to delete. That is, frequency of each element — 1. Let us call it extra.

If extra is even, answer is number of distinct elements, (cancel out the extras within themselves), or else, distinct elements — 1.

There is no English editorial.

Short editorial

C: 6, 5, 6, 5, 6, 5, 6, 5, ... is the optimal strategy

D: This operation can be described as "remove two arbitrary selected cards"

E: For each d,

• when r_i - l_i > d, i_th kind of souvenirs can be always purchased
• otherwise, there is at most one station where you can purchase i_th kind of souvenirs. It can be easily archieved by checking d, 2d, 3d, ...

F: I'm sorry for my poor English. It's tough for me to describe the idea of solution. Please check the Accepted code.