Read the time string.

If it is exactly 00:00, print okay; otherwise print poor.

Time complexity: $$$O(1)$$$.

The rating system is balanced if and only if the sum of all rating changes is equal to zero.

Read the array, compute its sum, and:

• print OK if the sum is $$$0$$$;
• print BUG otherwise.

Time complexity: $$$O(n)$$$.

Each group is independent.

A group gives its score only when all tests in this group are passed in the given attempt.

For every group $$$i$$$:

• read its test results;
• if all values are $$$1$$$, add $$$b_i$$$ to the answer.

Time complexity: $$$O(k_1 + k_2 + \dots + k_g)$$$.

Now there are several attempts, and results are merged by groups.

For each group $$$i$$$, keep solved[i].

While reading every attempt:

• if all tests of group $$$i$$$ are passed in this attempt, set solved[i] = true.

At the end, sum the scores of all solved groups.

Important detail: it is not enough that every test of a group passed in some attempt. The whole group must be passed inside one same attempt.

Time complexity: $$$O(m(k_1 + k_2 + \dots + k_g))$$$.

Sort all promos by (start time, index). This preserves the order in which promos enter the queue.

Simulate the carousel with a queue:

• time is the current time;
• if the queue is empty, jump time to the next promo start time;
• add all promos with $$$l_i \le time$$$ to the back of the queue;
• remove expired promos from the front while $$$r_i \lt time$$$;
• if the front promo is still active, it is shown from time to $$$r_i$$$, so its shown duration is $$$r_i - time + 1$$$;
• then set time = r_i + 1.

Every promo enters and leaves the queue at most once. After the simulation, output all indices with maximum shown duration.

Time complexity: $$$O(n \log n)$$$.

Call an edge $$$(i, i+1)$$$ bad if:

First count the initial number of bad edges.

If we change only one value $$$z_i$$$, only two edges can change:

• $$$(i-1, i)$$$;
• $$$(i, i+1)$$$.

So we can try every index independently.

For a fixed index $$$i$$$, we only need to check a constant number of candidate values:

• $$$1$$$ and $$$m$$$;
• current $$$z_i$$$;
• near the left threshold: $$$z_{i-1} - 1$$$, $$$z_{i-1}$$$;
• near the right threshold: $$$z_{i+1}$$$, $$$z_{i+1} + 1$$$.

Why is this enough? The left edge changes only around $$$z_{i-1}$$$, and the right edge changes only around $$$z_{i+1}$$$.

For each candidate, recompute only the affected local edges and keep the best answer.

Time complexity: $$$O(n)$$$.

Use the same local idea as in E1.

Changing one position affects only its adjacent edges. Therefore, changing two positions has two cases.

First compute single_gain[i]: how many bad edges can be removed by changing only position $$$i$$$.

If two changed positions are at distance at least $$$3$$$, their affected edge sets do not intersect. Their gains can simply be added. We can find the best such pair using suffix maximums.

The remaining cases are close pairs:

• $$$(i, i+1)$$$;
• $$$(i, i+2)$$$.

For these pairs, affected edges may overlap, so check them directly. For each of the two positions, use the same constant-size candidate set as in E1, and try all pairs of candidate values.

Let best_gain be the maximum possible decrease. The answer is:

Time complexity: $$$O(n)$$$.

Balls move on a line and cannot pass through each other. Therefore, the relative order of remaining balls never changes.

Suppose there are currently $$$k$$$ balls. Consider a ball whose current order among remaining balls is $$$r$$$ and whose target cell is $$$t$$$.

This ball can be removed if:

and

The first condition means the balls on the left fit into cells before $$$t$$$. The second condition means the balls on the right fit into cells after $$$t$$$.

If a ball is removable, removing it is always safe. It only decreases the number of blocking balls for all other balls.

Maintain two deficits for every ball:

• left deficit: $$$r - t$$$;
• right deficit: $$$(k-r) - (m-t)$$$.

A ball is ready if both deficits are non-positive.

When ball $$$i$$$ is removed:

• all balls to its right have one fewer ball on the left, so their left deficit decreases by $$$1$$$;
• all balls to its left have one fewer ball on the right, so their right deficit decreases by $$$1$$$.

Use two lazy segment trees to support these range decrements and to find newly ready balls. Put ready balls into a queue and process each ball at most once.

Time complexity: $$$O(n \log n)$$$, where $$$n$$$ is the number of balls.

A component uses the nearest override on the path from the root to this component. If no override exists on this path, it uses the global default value.

So query type 4 v asks for the deepest active ancestor of $$$v$$$.

Use Heavy-Light Decomposition on the tree.

Maintain a segment tree over HLD positions:

• if node $$$v$$$ has an override, store (depth[v], v) at its position;
• otherwise store (-1, -1).

Operations:

• 1 x: update the global default value;
• 2 v x: mark $$$v$$$ active and store its override value;
• 3 v: remove $$$v$$$ from the segment tree;
• 4 v: query all HLD segments on the path from root to $$$v$$$, take the pair with maximum depth, and output its value. If no active node exists, output the global default.

Time complexity:

• update: $$$O(\log n)$$$;
• query: $$$O(\log^2 n)$$$.

Let

Compute all initial score(s) values in $$$O(n)$$$:

When moving the start from $$$s$$$ to $$$s+1$$$, the first element gets coefficient $$$n$$$ instead of $$$1$$$, and all other coefficients decrease by $$$1$$$:

Now consider an update $$$a_p := x$$$. Let

For a fixed start $$$s$$$, the coefficient of $$$a_p$$$ is:

So every score receives a linear addition in $$$s$$$:

• for $$$s \in [1,p]$$$: add $$$-\Delta \cdot s + \Delta(p+1)$$$;
• for $$$s \in [p+1,n]$$$: add $$$-\Delta \cdot s + \Delta(p+n+1)$$$.

We need the maximum score after range linear additions.

Use sqrt decomposition over the score array. For each block store:

• raw score values;
• lazy linear function lazy_a * i + lazy_b;
• an upper hull of lines (m = i, b = raw_i).

For a whole-block linear update, only change the lazy values.

To get the block maximum, query the hull at x = lazy_a and add lazy_b.

For a partial block, push the lazy values into raw values, update the needed elements, and rebuild the hull.

Each carousel update affects two linear ranges, so all blocks can be updated efficiently.

Time complexity: about $$$O(\sqrt n \log n)$$$ per update.