Note that the correct greedy strategy is maintain your set of reachable nodes, and jump up high from the highest point in this set, recalculate the set of reachable nodes. To optimize this, we can make edges like $$$x \rightarrow $$$ highest point in set of reachable nodes of $$$x$$$.

First of all, let's discuss how to make these edges efficiently. We can sort the points in order of their heights, and then maintain an incremental DSU. When the current processing value is $$$A_i$$$, before uniting $$$i$$$ with all its neighbours, we will process and find the maximum values of nodes of components with $$$A_x \lt A_i - K$$$. ($$$K$$$ being jumping parameter)

Now, this reduces to a problem of the form : Find the first ancestor of $$$(A, B)$$$ such that it can reach $$$(C, D)$$$. We can directly use parallel binary search to solve this. The structure needed to maintain reachability is exactly the same as previous structure.

Complexity : $$$O(N \cdot log (N) \cdot alpha(N))$$$

The idea is to build a base sequence that you can recognize, and then insert numbers into that. What i did is first make $$$01010....$$$ with exactly $$$10$$$ 0s and $$$10$$$ 1s. Then, i assigned weights to the continuous runs, with the weights being $$$2^0, 2^0, 2^1, 2^1, 2^2, 2^2, ...$$$.

Once the base sequence is built, we can easily add things to it with the appropriate weight using at most $$$log(N)$$$ additional items. (Since we have options for both $$$0$$$s and $$$1$$$s). So this gets you a solution in $$$3 \cdot log(N)$$$

Handling the cases when there are less than $$$10$$$ $$$0$$$s or $$$10$$$ $$$1$$$s is slightly tricky (or there are $$$10$$$ 0s eventually, but they appear late), and the idea is to build the sequence like normal acting as if the base was complemented, but if the base had not been complemented, we can identify that in Bruno.

Some possible optimizations for higher points:

Use base $$$3$$$ for $$$4 \cdot log_3(N)$$$ instead of $$$3 \cdot log_2(N)$$$. Instead of assigning weights, you can do better by making a bijection (or near bijection) from all sequences such that $$$x_1 + x_2 + ... + x_k = m$$$, with $$$k$$$, $$$m$$$ being parameters, taking $$$k = m = log_4(N) + log(log(N))$$$ since there are $$$C(m + k, k)$$$ such sequences. You can get around $$$18$$$ (suggested by jtnydv25)

Suppose that only $$$(1, 1)$$$ and $$$(L, L)$$$ existed. let $$$C_i$$$ denote the cost to take $$$i$$$ to $$$(1, 1)$$$ and $$$D_i$$$ denote the cost to take $$$i$$$ to $$$(L, L)$$$. Then, $$$C_i + D_i = 4 \cdot (L - 1)$$$, i.e. their sum is constant. This is a powerful constraint, because it means that sorted by $$$C - D$$$ is valid, and then take a prefix of those and send them to $$$(1, 1)$$$ and the others to $$$(L, L)$$$.

This solves the problem in $$$2^N$$$ if we bruteforce on the mask that goes to $$$(1, 1)$$$ or $$$(L, L)$$$ while the rest go to $$$(1, L)$$$ or $$$(L, 1)$$$ and we can greedy each side.

Let us sort the sequence by $$$cost(1, 1) - cost(L, L)$$$. Then all the positions that go to $$$(1, 1)$$$ will occur before all the positions that go to $$$(L, L)$$$. Similarly, sorting by $$$cost(1, L) - cost(L, 1)$$$ gives us a similiar result.

Now, the crucial idea is that, every solution can be described with $$$2$$$ variables $$$b_0$$$ and $$$b_1$$$ (border variables) where if an index $$$i$$$ can go to $$$(1, 1)$$$ if and only if $$$i \le b_0$$$ in the first sorted order. While $$$i$$$ can go $$$(1, L)$$$ if and only if $$$i \le b_1$$$ in the second sorted order.

This divides the group of nodes into $$$4$$$ distinct groups, each having exactly $$$2$$$ choices, for example either $$$(1, 1)$$$ or $$$(1, L)$$$.

Fix the variables $$$b_0$$$ and $$$b_1$$$ and then for each group, do a dynamic programming dp[time used up of first kind] = minimum time of second kind, of infinity. Calculate this in $$$O(NT)$$$ per state.

After this, to check whether a solution is possible, note that it is a cyclic type structure. Let us fix the amount of $$$(1, 1)$$$ used up in the group of $$${(1, 1), (1, L)}$$$. This will also tell me how much I have left of $$$(1, L)$$$ which I can only use in the group of $$${(1, L), (L, L)}$$$, which then gives me the value for $$${(L, L), (L, 1)}$$$ and that finally gives me the value for $$${(L, 1), (1, 1)}$$$. Check for no infinity results and the sum of $$$(1, 1)$$$ used is $$$\le T$$$.

Naively, this is $$$O(N^3 \cdot T)$$$ since we fix $$$b_1$$$ (gets $$$81$$$ points surprisingly), but we can make this $$$O(N^2 \cdot T)$$$ by building prefix and suffix dps, instead of fixing $$$p_1$$$ since there are not many updates.

Note that either $$$(A, B)$$$ or $$$(B, A)$$$ is always achievable. The bad counter is the number of pairs such that both is not achievable. For this, either both $$$A$$$ appear before both $$$B$$$ or vice versa.

Further, the claim is that in $$$1$$$ move, we can always make the bad counter smaller by $$$1$$$. Proof : Consider the right endpoint of some $$$A$$$, say $$$X$$$, such that there exists $$$B$$$ whose first occurrence appears to the right of second occurrence of $$$A$$$. Either $$$X + 1$$$ is the right endpoint of some colour, or $$$X + 1$$$ is the left endpoint of some colour. If it is the left endpoint, swap and we are done. If it is the right endpoint, reconsider the process with $$$X + 1$$$ being our new variable $$$X$$$, and we are still guaranteed to have some colour completely on the right. Eventually this process stops.

Now, we need to calculate $$$D_i$$$ = number of good pairs for each cyclic subarray $$$[i, i + 2 \cdot N)$$$. This is fairly standard through a fenwick sweepline. For answering queries, there are $$$2$$$ options, either take the minimum cost of someone who has $$$D_i \ge K$$$ (trivial) or take the minimum cost of someone with $$$D_i \lt K$$$ in which case the cost is $$$C_i + (K - D_i) \cdot X$$$, i.e. store minimum value of $$$C_i - D_i \cdot X$$$ and add $$$K \cdot X$$$ to it.

Everything can be done in $$$O((N + Q) \cdot log(N))$$$.

Let's solve $$$N = 32$$$.

The idea is to first make groups of $$$2$$$ based on the first $$$4$$$ most significant bits being equal. We can query $$$i \oplus 1$$$, and now we will have $$$2$$$ people who know the special person.

After this, make groups of $$$4$$$ based on first $$$3$$$ more significant bits. Query $$$i \oplus 2$$$. If you already know the special person, indicate that with a $$$1$$$, otherwise put $$$0$$$. But, you also need to make these other $$$2$$$ people aware of the $$$0$$$-th bit as well, so this takes an extra turn.

If you solve like this, you will get a log^2 solution. But, we can parallelize the steps, and have the information passing in multiple steps at the same time to get a solution with asymptotic 2 * log. The details are left as an exercise to the reader.

For $$$n = 48$$$, make $$$3$$$ groups of $$$16$$$ at the end, and then exactly one of the groups know the special person. So, make one query to figure out which group this is.

For the type $$$1$$$ queries, let's maintain a small to large by depth. Each type $$$1$$$ query of the form $$$(X, Y)$$$, we merge depth $$$X$$$ array into $$$Y$$$ array. Type $$$2$$$ query, we create a new object and insert it in the appropriate depth.

Note that for a type $$$3$$$ query, we care about the sum of values in the set of your depth such that they lie in your subtree, i.e. a range query. So we can solve this with maintaining a structure to answer range sum quickly definitely (like implicit segment tree), but this wont fit the limits.

Instead, we can pop all the elements lying in $$$[tin_x, tout_x]$$$, find the sum naively and then only reinsert one element of the form $$$(tin_x, total)$$$. Each element only gets killed once, so this has asymptotic of $$$O((N + Q)log^2)$$$ with a fast constant factor.

Find a greedy strategy that works (and can also be optimized).

Here is one that works: at each step, take the right most occurrence of the smallest element that does not break the "prefix sum >= 0" condition. Proof is left as an exercise.

So, in essence, we will make some suffix of the "occurrences of x" as multiplied by $$$-1$$$. We can binary search this border in increasing order of $$$x$$$ and check if its valid in $$$O(NA^2 log)$$$ somewhat naively (by maintaining previous borders of $$$ \lt x$$$, and finding sums and min prefix sums of the ranges).

There are $$$2$$$ main ideas involved in the previous section to actually solve in $$$O(NA^2 log)$$$. First of all, the borders are only increasing obviously. This means that all elements $$$\le x$$$ to the right of the border must be negative. So we can find the minimum prefix sum starting from the border $$$b$$$ efficiently by precomputing prefix sum arrays treating $$$\le x$$$ as negative, and $$$ \gt x$$$ as positive. The sum before the border is trivial to compute in $$$O(NA^2 log)$$$

To optimize, the slow step is "finding sum before border", and here we again use the fact that borders are increasing. The sum looks like $$$pref_{(mid - 1, i)} - pref_{(b_i - 1, i)}$$$. We can maintan the $$$2$$$ quantities separately to get $$$O(NA log)$$$

The limits are very tight (for my solution at least), but it passed eventually

Who saw $$$Nlog^2(N)$$$ solution and seriously put $$$N = 2 \cdot 10^6$$$??? Why? Did you really need to block sqrt that much? Please set reasonable limits and not "well it runs in time, so its fine". If it lets some lesser solutions pass, that's preferable.

On C as well, I had to optimize $$$O(NA log)$$$ for more than an hour to pass. Probably missed 300 on Day $$$4$$$ due to this. I doubt intended solution is better in complexity, so maybe more lenient constraints? (or at least make subtasks with less constant optimized solutions..)

In both problems, I doubt better solutions are intended complexity wise (and even if it is, most people did not do it), so I was pretty annoyed. Nevertheless, I enjoyed the contests very much.

Our goal is to find a way to direct all the edges (without cylces) that we get a positive answer(path A->B exists).

After we find it (ill explain how to do it later) we can easily find vertex A by making topo-sort (lets call the sorted array T) on this directed graph and then binary search. We'll check if vertex A is before mid in T or after by reversing all the outgoing edges of T[1] up to T[mid] (we obtain first negative answer if mid = A). Same idea is used in finding B so we'll use up to 2logN queries

So how to find correct direction of our edges?

Tree solution (80 pkt): lets solve it using centroid decomposition, suppose we find centroid v after that we want to group all his subtrees in 3 groups that sum of vertecies in each of them is <= size / 2 (that can be easily done with some greedy) lets call those gropus X, Y and Z then we'll use 3 queries:

• make all edges from X go towards centroid v and rest in oposite direction
• make all edges from Y go towards centroid v and rest in oposite direction
• make all edges from Z go towards centroid v and rest in oposite direction

if we get a yes on any of these we finish if not it means that both A and B are in the same group! so we just recurse and use up to 3logN queries.

In implementation we cannot really recurse we need to code this centroid decomposition in "pararell" using same layers and computing all 3 queries for each of the current centroids at once but its not that hard.

Full optimalization: Find some random spanning tree using DSU.

When asking queries in centoird part just direct all non-tree edges that will not ruin our DAG (when theres non-tree edge in same "centoird part" it wont change our reachability but when theres an edge between different centoird parts that we're solving in pararell, it won't matter cause if it would make B reachable from A we would not recurse in the first place)

Total queries used: 5logN = 70

My code: https://qoj.ac/submission/2311253