Editorial for Pile of Crabs

This problem can be solved using SegmentSegment TreeTree.
First, take an array sized N+QN + Q. Let’s populate the array with crabs according to their numbering. Only NN indices will be filled and the last QQ indexes will remain empty. For each event, we will take a crab, and place it after the last used index. And we will have to keep track of their health.

This whole process can be done using SegmentSegment TreeTree with LazyLazy PropagationPropagation. Our Segment tree will have the following properties:

  • Each node will save that if there any health decrease update for this range of crabs for lazy updates.

  • Check the health of crab numbered XX.

  • Decrease the health of all crabs after the position of crab XX to the crab placed at the top of the pile. We will save the update of decrease as a lazy value for our desired range.

  • Place crab XX after the current crab, that is on the top of the pile.

Statistics


77% Solution Ratio

towfiq379Earliest, 9M ago

MursaleenFastest, 0.2s

pathanLightest, 11 MB

MursaleenShortest, 738B

Toph uses cookies. By continuing you agree to our Cookie Policy.