I was resolving that data structures problem, 669E - Little Artem and Time Machine using fenwick tree. As you can see in this submission 280626744, each fenwick tree node have a map, that describe the frequency of elements in that moment. During addition, I have carefully merged nodes by merging the node with a map of small size into the other. But I am getting TLE on testcase 6.

Do someone know why the complexity of my solution is not $$$O(n * log(n)^2)$$$, as for $$$O(n * log(n))$$$ for the fenwick and the $$$O(log(n))$$$ for the merging process? Also as I know fenwick tree don't have a big constant factor.

Each time, I faced a heavy implementation problems, even If I had the idea of the solution earlier, I just lost myself in the process of resolving, and look at the editorial many times. Every time, I missed a detail, and that took me sometimes 30 minutes without even remark it. Suddenly when I look at the editorial again, I say oh what the hell? and repeat the same process, again and again.

I am so slow on heavy implementation, and I know the common advice is to solve more implementation problems, but I am trying that and it's hard as described before. Did someone faced the same problem, and overcomed it? At least for implementation problems in range 1800 — 2000. If yes please give me advice, how should I trained this type of problems.

Also any tips to become quicker on resolving problems in general is welcome.

Given a list of interval, find the maximum difference between two intervals. The difference between two intervals A and B is the number of element that are in A and not in B, or in B and not in A.

UDP : It mean element that are exactly only in one of A and B

Can it be found in O(n) ?

I was resolving 1922D - Berserk Monsters, and I found that access to the prev of beginning of set doesn't through wrong answer and can't get why.

First as you can see in that sumbmission that give wrong answer 264232760, I put the defense of border element at N = 2e9 + 5, and their attacks at 0 so they can't die neither attack. I took that value because 2*1e9 < N.

But in the editorial they took INT_MAX which is 2147483647 and it worked as you see here 264232643. I could not get why it's working, and after some times, I remark that if for the example the border 0 is in live set, it would be at the beginning of the set, and the code tried to access to predecessor of it, after and got the predecessor, it use that value as array index, which would normally leads to runtime error, but I get it gave a value which can be more than 1e9, it's for that reason N = 2e9 + 5 is not sufficient to prevent border to die.

Can someone explain why predecessor of the beginning of a set doesn't lead to runtime error, and why it's work?

For the problem 1822G1 - Магические тройки (простая версия), I submitted this code 261212704 that return TLE. The complexity of this is O(n * sqrt( Max)) which leads to 10^8 operations, so that code must passed when using c++ with basic operations.

After looked at the editorial, it's the same logic with same complexity, and after submitted the editorial code 261212704, I got accepted. Can someone find what's wrong? Thanks in advance

You can find the problem there 1930F - Maximize the Difference.

Before you continue the reading, this is my first blog, I don't know how to write mathematical formulas with codeforces, as for example maximum over a set. If any advice for this it will be helpful.

Problem statement

Given an array b of m non-negative integers, we must calculate f(b) as the maximum value of max(bi|x)−min(bi|x) over all possible non-negative integers x.

And as hints, the editorial mention :

1. For an array b consiting of m non-negative integers, f(b)=max(max(bi|bp)−min(bi|bp))

2. f(b) is the maximum value of bi ∧ ~ bj over all pairs

If you have any solution feel free to comment on it. Thanks!!!