My step-by-step barbell moving (though improved to add into under and out under the barbell only "right" worms without checking every worm) gives TLE on 8th test.

Is segment tree needed?

I solved without it.I also used "improved step-by-step barbell moving",but my solution was quite far from TLE. I modeled groove as int array,but if you use sorting on worms array and then search there some coordinates then you can possibly get TLE.

Edited by author 06.03.2009 05:20

I solved this problem without sorting. I found difference
d[this_step]=count[this_step]-count[prev_step],
and after that
count_squash_worm=count_squash_worm+d[this_step].

Edited by author 09.03.2009 15:06

Just slide ahead and once you step on a worm by left or right plate, increase number of times that worm was stepped on (that number will drift between 0, 1, 2). When number of plates intersecting the worm changes between 0 and 1, total amount of affected worms changes accordingly. This algo can support overlapping worms and 1e+9 coordinates with sorting of worm endpoints.