Maniacal Midsummer Marathon 2014 by AL, TL, JJ
Esdeath is currently enjoying a wonderful dinner with subordinates in
her army. There is a giant pot on a campfire, and
soldiers surrounding the pot in a circle, numbered clockwise
from
to
. Each soldier holds a very large supply of a specific type
of food that tastes best when cooked at a specific range of
temperatures. Soldier
's food tastes best when it is cooked between
and
degrees Celsius, inclusive. We shall refer to this
as the optimal temperature range.
The entire campfire cooking session will last
minutes. During each of these minutes, one of three possible
events will occur:
Esdeath would like to try a combination of foods, so all soldiers with a number between
and
(
; note: it is not necessarily true that
) will pitch in some food if the type of food they hold tastes best within a certain range of the pot's current temperature
degrees Celsius. That is, if a soldier is between soldiers
and
inclusive, they must contribute if their optimal temperature range overlaps with the range
. Here, between means starting from the
soldier and going clockwise around the circle, considering every soldier you pass up to and including the
soldier.
After each time Esdeath performs this event, the temperature of the pot will change based on three constant values
,
, and
. The new temperature after each instance of this event is determined by the formula:
, where
is the number of foods tossed into the pot. We'll assume that each soldier has a very large quantity of their own type of food, and will always be able to contribute if his or her temperature range is right. Every time this event is called, please determine
, the number of types of foods that have been tossed into the pot.
The
soldier gets a new type of food, getting rid of their old type of food. The new type of food will have an optimal temperature range between
and
.
For this event, Esdeath would like to know, hypothetically, if all soldiers between
and
were to put some of their food into the pot in increasing order of the
temperatures of their food (the lower bounds of their foods' optimal temperature ranges), what would be the
temperature of the
soldier who places food into the pot? If no such value exists, output
-1
.
Input Specification
Line : Six integers
,
,
,
,
, and
.
Next lines: line
will contain two integers
and
,
the optimal temperature range for soldier
's initial type of food.
Next lines: line
will describe the event that happens in
the
minute of the cooking session. Each line will be in one of
the following three formats to represent the three types of events:
- Type
events will be in the format:
1 i j L H
- Type
events will be in the format:
2 i L H
- Type
events will be in the format:
3 i j k
At any given time the pot's temperature will satisfy
.
Furthermore, the total number of type
events will not exceed
.
Sample Input 1
5 4 4 1 1 10
1 3
4 6
7 9
3 5
2 4
1 1 5 1 0
1 2 4 0 0
1 3 3 0 0
1 3 2 0 0
Sample Output 1
4
1
0
2
Sample Explanation 1
The pot starts at a temperature of degrees Celsius. The range of
temperatures is
.
All soldiers participate, and types of food are thrown into the pot.
The temperature becomes
degrees Celsius.
Soldiers ,
, and
participate, and
type of food is thrown into the
pot. The temperature becomes
degrees
Celsius.
The third soldier cannot throw any food into the pot. The temperature
becomes degrees Celsius.
All soldiers participate again, and types of food are thrown into the
pot. The temperature becomes
degrees Celsius,
and the cooking session ends.
Sample Input 2
3 10 1 2 3 10
1 1
1 5
1 10
1 1 3 0 9
2 3 10 10
1 1 3 1 1
1 1 3 0 9
1 1 3 0 1
2 2 9 9
1 1 3 0 2
1 1 3 2 0
1 1 2 0 0
1 1 2 0 0
Sample Output 2
3
2
3
1
2
1
0
1
Sample Input 3
5 12 1 0 0 5
3 3
1 1
3 3
4 4
2 2
3 1 5 1
3 2 1 2
3 3 2 3
3 4 3 4
3 5 4 5
3 1 3 1
3 1 3 2
3 1 3 3
3 4 2 4
3 1 2 3
3 4 1 5
3 4 1 2
Sample Output 3
1
2
3
3
4
1
3
3
4
-1
-1
3
Constraints
Subtask 1 [8%]
Additionally, there will be no events of type .
Subtask 2 [17%]
In all events of type ,
.
Additionally, there will be no events of type .
Subtask 3 [20%]
and
.
Additionally, there will be no events of type .
Subtask 4 [15%]
There will only be events of type .
Subtask 5 [17%]
There will be no events of type .
Subtask 6 [20%]
Subtask 7 [3%]
There are no additional constraints.
Comments