Indian Computing Olympiad

Range Queries→Mountain (IOI 2005)

The Mountain Amusement Park has opened a brand-new simulated roller coaster. The simulated track consists of n rails attached end-to-end with the beginning of the first rail fixed at elevation 0. Byteman, the operator, can reconfigure the track at will by adjusting the elevation change over a number of consecutive rails. The elevation change over other rails is not affected . Each time rails are adjusted, the following track is raised or lowered as necessary to connect the track while maintaining the start at elevation 0. The figures below illustrates two example track reconfiguration s.

Each ride is initiated by launching the car with sufficient energy to reach height h. That is, the car will continue to travel as long as the elevation of the track does not exceed h, and as long as the end of the track is not reached.

Given the record for all the day's rides and track configuration changes, compute for each ride the number of rails traversed by the car before it stops.

Internally, the simulator represents the track as a sequence of n elevation changes, one for each rail. The i-th number di represents the elevation change (in centimetres) over the i-th rail. Suppose that after traversing i-1 rails the car has reached an elevation of h centimetres. After traversing i rails the car will have reached an elevation of h + di centimetres.

Initially the rails are horizontal; that is, di = 0 for all i. Rides and reconfigurations are interleaved throughout the day. Each reconfiguration is specified by three number s: a, b and D. The segment to be adjusted consists of rails a through b (inclusive). The elevation change over each rail in the segment is set to D. That is, di = D for all a ≤ i ≤ b.

Each ride is specified by one number h - the maximum height that the car can reach.

Inputs are of the form:

• I a b D – reconfigure segments a to b to D
• Q h – start a ride with energy level h
• E – end of input

        0       0       0       0        <- elevation change in segment
            0       0       0            <- elevation of endpoint
    *-------*-------*-------*-------*
        1       2       3       4        <- segment id
      

                                <---------- elevation change in segment
                              2     8 <---- elevation of endpoint
                                    *
                      2     6
                            *
              2     4
                    *
      2     2
            *

    *-------o-------o-------o-------o
        1       2       3       4
      

                               2    5
                                    *
                       2    3
                            *
       2    2   -1
            *       1
                    *
    *-------o-------o-------o-------o
        1       2       3       4