Editorial for COCI '08 Regional #6 Cvjetici

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Simulating the growth of plants by maintaining a two-dimensional table is of time and space complexity $\mathcal O(N^2+NM)$ ~\mathcal O(N^2+NM)~, where $M$ ~M~ is the maximum coordinate. This solution scores 30 points.

Let $A(x)$ ~A(x)~ be the number of plants for which a flower may grow at coordinate $x$ ~x~ (but hasn't yet). The sequence $A$ ~A~ initially contains all zeros and changes when plant $(L, R)$ ~(L, R)~ grows:

Flowers will grow at coordinates $L$ ~L~ and $R$ ~R~, a total of $A(L)+A(R)$ ~A(L)+A(R)~ of them, so we output that number. After these flowers have grown, there are no more available plants at coordinates $L$ ~L~ and $R$ ~R~, so we reset $A(L)$ ~A(L)~ and $A(R)$ ~A(R)~ to zero.
The horizontal segment $[L+1, R-1]$ ~[L+1, R-1]~ is now available to grow flowers, so we increase $A(x)$ ~A(x)~ by one for each of those coordinates.

Directly implementing the above algorithm yields a solution of complexity $\mathcal O(NM)$ ~\mathcal O(NM)~, scoring 45 points.

For full score, we need a data structure that supports the following operations:

Set $A(x) = 0$ ~A(x) = 0~;
Increase $A(x)$ ~A(x)~ by one for each $x$ ~x~ in $[L-1, R+1]$ ~[L-1, R+1]~.

Some of the data structures that do this are interval trees and Fenwick trees for $\mathcal O(\log N)$ ~\mathcal O(\log N)~ per query, or splitting the sequence $A$ ~A~ into blocks of size about $\sqrt N$ ~\sqrt N~, for $\mathcal O(\sqrt N)$ ~\mathcal O(\sqrt N)~ per query. See task Jagoda for details on this structure.

Comments

There are no comments at the moment.