Editorial for COCI '12 Contest 6 #4 Burek
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Let us take a look only at the cuts (solution for cuts is analogous).
Notice the pastries that are cut by a line are not completely left nor completely right to the line. The solution for this line is therefore:
We will calculate the function values of and before reading the cuts (therefore answering to each cut in a constant time complexity). We calculate the values using the following relation:
and an analogous relation for the second function. We read the values of the auxiliary function from an array whose elements we increase during the input of the pastries.
An alternative solution uses a sweep-line algorithm and is left as an exercise to the reader.
Comments