I guess the sufficient condition is that:

t[i] is the time of i-th player plays.

1.0 ≤ t[i] ≤ M.

2.sum(t[i]) = 6 * M.

I think the following greedy works, but I don't have proof: let's sort the players by quality. Then make a 6 × n table (so it has 6 rows and n columns) and from left to right fill it greedily with players not exhausting their endurance. From this matrix calculate the needed things.

Results are out!

Insert all passwords into a trie and then use bruteforce to check every substring of every password.

For storing strings use unordered_map which is basically hashing

Simple std::map passes too. I stored count of strings in a map, checked every substring of every string, and multiplied by the counts. It results in O(NM²log(N)) complexity, where M is the length of the strings, so about 3 * 10⁷ operations. My solution passed with 0.49 s on worst case.

I coded such a solution and got full points (slowest time 0.46s). Code

Seems is intended. Sort the events and queries offline by values of x (number of stops) and process the remaining dimension (children's age) with a segment tree.

It probably means you bring down and up the same person at one moment, which is illegal. So instead of a -  > b you do c -  > a, a -  > b.

Do you remember the rule "but a player cannot enter the game, and then exit in the same moment, or vice versa"?

I wasn’t able to participate, so this might get wrong

As the rectangles form a tree structure, our task is simplified to

• Building trees
• Querying for a node that contains given points

If we do these fast, other stuffs are fairly easy.

We can use sweep line to do that. In a BST (std::set) we store rectangle as an interval, sorted in order of lower y coordinate. To build a tree, we just need to find a parent. This can be done by lower_bound operation in insertion phase (lower y coordinate slightly less than current interval). Query can be done in simillar way. So this is solvable in O((n+m)lgn)

You build a tree of the rectangles (they are the vertices). By this I mean that the parent of rectangle X is the smallest rectangle Y, which contains X inside of it. This can be done with sweep line on the X-axis using a segment tree for the Y-axis in time.

Now for every paintball ball we find the smallest rectangle containing it. After that we add that we have colored this rectangle with color of the given ball (we simply add it to a vector for this rectangle or something like that). This again can be done in with sweep line in time.

Well now we have a tree and some vertices already have colors for them. Well if we have colored vertex X in some color, all of its ancestors also are colored with the same color. From this we see that a rectangle (vertex) is colored with all colors in it's sub tree. This is a well known problem which can be solved in with a segment tree and DFS order or with "dsu on tree" (I used this).

So the whole solution has running time of . Here is my AC code from the competition.

PS: In my code both sweep lines are merged into one.