I discussed with tmw and it seems the following construction works:

Checkerboard all possible bench locations. On one color, draw a road directly above if possible, otherwise try to draw a road directly below it. On the other color, draw a road directly to the left if possible, otherwise try to draw a road directly to the right.

For every pair of adjacent fountains, lets assign a bench that can take care of the road between them if it is built. Firstly, we split the coordinate plane into 2x2 grids and colour them with chessboard pattern. The center of each square is a candidate position of a bench, denoted with a pink cross in the figure. For each black square, we want the center to be responsible for the roads vertically above and below it, and for each white square, we want the center to be responsible for the roads left and right of it. That is, in the figure, we want each pink cross to take care of the two candidate roads that is touched by the pink line passing through it.

Now, lets solve subtask 5, where there are no 4 fountains forming a 2x2 square. We can consider all roads that we can possibly build, and if they dont form connected component we know answer is 0. Otherwise, lets find a spanning tree. Then, for each road that is in the tree, we will assign it to the bench that is responsible for it from the previous paragraph. Because there are no 2x2 squares, we know that each bench will only take care of at most 1 road and therefore we find a solution.

To get full solution, we want to stop considering some candidate roads so that:

1) Each bench is responsible for 1 candidate road only.

2) The fountains remain connected.

Lets consider all 2x2 squares where there is a fountain in all 4 corners. We will build dual graph, which is a graph with these 2x2 squares as vertices along with an additional vertex representing the outside region. Then, for each of these 2x2 squares $$$u$$$, there are two roads where the center is responsible for. If we walk through each of these edges, we will reach another vertex $$$v$$$. Lets build edge from $$$v$$$ to $$$u$$$.

Now, we will run a dfs from the outside vertex. It can be easily seen that we will reach all vertices, and thus we will get a dfs tree spanning all vertices. Now, we know that each edge in this spanning tree cuts a candidate road. Lets stop considering these roads that are cut. We can make such observations:

1) A spanning forest of fountains that belong to at least one 2x2 square remains. You can refer to the proof of $$$V-E+F=1+C$$$ to understand this. With this result we know that even after cutting, the connectivity of the graph doesnt change.

2) For each bench that are originally responsible for 2 candidate roads, we will cut at least one of them, because we need to pass through at least one of them to enter that 2x2 square.

Thus we can just continue with the new graph and plug solution for subtask 5 to finish the problem.

Or not, cuz people were faster than me.

is there scoreboard available ?

Disregard, wrong problem oops --https://mirror.codeforces.com/blog/entry/92083?#comment-807698--

Oops disregard my earlier comment, that's problem C. For A (candies), there are 2 main ideas. The first is pretty simple: the operations are somewhat complicated, but we have all operations upfront, so we can "transpose" the problem. We'll maintain a segtree of updates indexed by time and we'll sweep through indices, answering one query at a time. As we sweep past $$$l[i]$$$ and $$$r[i]$$$, we will enable and disable the update at time $$$i$$$ in our segtree. This way, when we want to answer a query, we'll have all the updates available at once.

Thus, we just have to solve the $$$n=1$$$ version (in a way compatible with enabling/disabling on a segment tree). (This is pretty much subtask 4.) Here's an alternative view of updates. Think about the sequence of updates as a line graph, moving up-right or down-right, ignoring the lower and upper bounds, and think of the two bounds as horizontal walls. Then, if the line hits a wall, it pushes the walls along as it continues moving, and the answer is just where the line ends up relative to the walls. It's pretty easy to figure out where the line ends up (that's just the total of all updates), so we just want to figure out where the walls end up.

Now, let's think about the last time the line touches a wall. (We can force it to touch both walls at least once by adding dummy $$$v[-2] = +\infty$$$ and $$$v[-1] = -\infty$$$ updates, or we can just handle the case where it doesn't touch both walls as a special case.) WLOG, it touches the upper wall last, and let's say it's at time $$$t_u$$$ and height $$$h$$$. Then, after $$$t_u$$$, everything must stay within the interval $$$(h-c, h)$$$. Furthermore, it must touch the lower wall some time prior to it, and that last lower wall touch must be $$$\le h-c$$$, otherwise height $$$h$$$ won't be able to touch the upper wall. If we think about the last time $$$t_l$$$ where we're at height $$$h-c$$$, then between $$$t_l$$$ and $$$t_u$$$, everything must stay in $$$(h-c, h]$$$; we can't go below because $$$t_l$$$ is the last time at height $$$h-c$$$, and we can't go above because we're not allowed to do any more lower-wall-touches to bring the range back down. Thus, in the time range $$$(t_l, \infty)$$$, we stay within $$$(h-c, h]$$$ and hit $$$h$$$ exactly, so we can actually identify $$$t_l$$$ as the maximum time such that $$$\max_{t \in [t_l, \infty)} h(t) - \min_{t \in [t_l, \infty)} h(t) = c$$$, and then that interval is exactly where the walls end up (the answer is $$$h(\infty) - \min_{t \in [t_l, \infty)} h(t)$$$).

Thus, we just have to find this maximum time such that the suffix of the line graph has range $$$c$$$. Note that this $$$\max - \min$$$ range is increasing as we decrease $$$t_l$$$, because we're taking $$$\max$$$ and $$$\min$$$ of more elements. We can do this by binary searching on a segment tree of updates where we store maximum/minimum prefix sums (note that $$$h(t)$$$ is just a prefix sum of updates). This also easily supports enable/disable. The approach above assumes we can split a $$$v = +2$$$ update into two $$$v = +1$$$ updates, which is pretty easy to do implicitly.

This problem is somewhat similar to JOI 2021 Spring Camp foodcourt, and I'm pretty sure I've seen this exact touch-2-walls structure before in a different contest; maybe someone else remembers the problem.

Problem A can also be solved on-line in time $$$O(Q \sqrt{N})$$$ using square root decomposition. We begin by "standardly" partitioning our array into blocks of size $$$\sqrt{N}$$$. Afterwards, each query will affect some blocks completely, and (at most 2) blocks partially. Let's bulk the operations for each of the blocks. We'll implement a procedure called Commit(block) which will "commit" all updates.

How to write this procedure?

Let's keep a function $$$f(x)$$$ where $$$f(x)$$$ is the final number of candies for an (initially empty) box with capacity $$$x$$$. This function looks like an increasing piecewise linear function, where slopes alternate between $$$0$$$ and $$$1$$$. We can update $$$f$$$ after a new operation by keeping track of the points where the slope changes in a stack.

Now, the least beautiful part about this approach is that computing function $$$f$$$ is not enough, because some boxes might have leftovers from earlier updates (they are not empty). But we can adapt it by noticing that the final number of candies for a box with capacity $$$c_i$$$ and $$$a_i$$$ initial candies is:

$$$a'_i = \max(0, \min(c_i - maxd, a_i) + mind) + f(c_i)$$$

Where $$$mind$$$ is the minimum delta over the current operations ($$$mind < 0$$$) and $$$maxd$$$ is the maximum delta. The reasoning is somewhere in the lines of:

"If $$$a_i + maxd > c_i$$$, then $$$a_i$$$ could have been $$$a_i - 1$$$ and the final answer wouldn't change. Also, if $$$a_i + mind < 0$$$, then $$$a_i$$$ could have been $$$0$$$ to begin with."

Unfortunately, the memory is also $$$O(Q \sqrt{N})$$$, which makes the solution risking both MLE and TLE, but after some little tinkering with the constant, it gets AC with 4s. The memory can be optimized to $$$O(Q + N)$$$ if you commit one block when there are more than $$$\sqrt{N}$$$ operations which affect it, though this was not necessary.

Source code: https://pastebin.com/HA7FJqaC

Note that the number of candies in each box will never decrease. That means that when the limit for one box is reached, it can't go higher. So we can calculate the number of candies in each box disregarding the limit constraint with prefix sums, and if $$$ans[i]$$$ is the number of candies in box $$$i$$$ in this case, we have $$$s[i] = \min(ans[i], c[i])$$$.

All queries are add. So just do offline range add with prefix sums.

vector<long long> pref(n+1);
for (int i = 0; i < v.size(); i++) {
	pref[l[i]] += v[i];
	pref[r[i]+1] -= v[i];
}

vector<int> ans;
for (int i = 0; i < c.size(); i++) {
	if (i > 0) pref[i] += pref[i-1];

	ans.push_back(min(1LL*c[i], pref[i]));
}
return ans;

I wonder who that friend is...

Nice that two Serbian tasks were on the same day of IOI, who knew IOI day 1 would be Serbian Olympiad in Informatics Open Contest :)

really exciting to see how OM problems can be used in OI and vice versa. A few days ago I saw a comment about IMO'19 Problem 5 being used for a recent OpenCup Contest.

Rain Jiang

anyone ?

For sub3 use Segment Tree Beats

In sub4, if we sort array C, then after each query each element of some prefix will be set either to zero or to its max value(C[i]), and all other elements will be increased by v. For that, we can maintain a lazy segtree with range updates(set some segment to 0, set some segment to max value, add some value to a segment) and find the prefix for queries with binary search. Code: link

I think that you should use long long int