Maniacal Midsummer Marathon 2014 by AL, TL, JJ
Problem G: Campfire Cooking
Esdeath is currently enjoying a wonderful dinner with subordinates in her army. There is a giant pot on a campfire, and N (2 ≤ N ≤ 200000) soldiers surrounding the pot in a circle, numbered clockwise from 1 to N. 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 i's food tastes best when it is cooked between A_{i} and B_{i} degrees Celsius, inclusive. We shall refer to this as the optimal temperature range.
The entire campfire cooking session will last M (1 ≤ M ≤ 200000) 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 i and j (1 ≤ i, j ≤ N; note: it is not necessarily true that i ≤ j) will pitch in some food if the type of food they hold tastes best within a certain range of the pot's current temperature T degrees Celsius. That is, if a soldier is between soldiers i and j inclusive, they must contribute if their optimal temperature range overlaps with the range [T − L, T + H] (0 ≤ L, H ≤ 100000). Here, between means starting from the ith soldier and going clockwise around the circle, considering every soldier you pass up to and including the jth soldier.
After each time Esdeath performs this event, the temperature of the pot will change based on three constant values X, Y, and Z (0 ≤ X, Y ≤ 1000; 1 ≤ Z ≤ 100000). The new temperature after each instance of this event is determined by the formula: T_{new} = ((T_{old}*X + F*Y) mod Z) + 1, where F 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 F, the number of types of foods that have been tossed into the pot.
The ith 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 L and H (1 ≤ i ≤ N; 1 ≤ L ≤ H ≤ Z).
 For this event, Esdeath would like to know, hypothetically, if all soldiers between i and j were to put some of their food into the pot in increasing order of the A_{i} temperatures of their food (the lower bounds of their foods' optimal temperature ranges), what would be the A_{i} temperature of the kth soldier who places food into the pot? If no such value exists, output
1
.
Input Format
Line 1: Six integers N, M, T, X, Y, and Z.
Next N lines: line i+1 will contain two integers A_{i} and B_{i}, the optimal temperature range for soldier i's initial type of food.
Next M lines: line i+N+1 will describe the event that happens in the ith minute of the cooking session. Each line will be in one of the following three formats to represent the three types of events:
 Type 1 events will be in the format:
1 i j L H
 Type 2 events will be in the format:
2 i L H
 Type 3 events will be in the format:
3 i j k
At any given time the pot's temperature T will satisfy 1 ≤ T ≤ Z. Furthermore, the total number of type 2 events will not exceed 25000.
Sample Input 15 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 Input 23 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 Input 35 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 14 1 0 2 
Sample Output 23 2 3 1 2 1 0 1 
Sample Output 31 2 3 3 4 1 3 3 4 1 1 3 
Explanation for Sample 1
The pot starts at a temperature of 4 degrees Celsius. The range of temperatures is [3, 4].
All soldiers participate, and 4 types of food are thrown into the pot. The temperature becomes (4*1 + 4*1) mod 10 + 1 = 9 degrees Celsius.
Soldiers 2, 3, and 4 participate, and 1 type of food is thrown into the pot. The temperature becomes (9*1 + 1*1) mod 10 + 1 = 1 degrees Celsius.
The third soldier cannot throw any food into the pot. The temperature becomes (1*1 + 0*1) mod 10 + 1 = 2 degrees Celsius.
All soldiers participate again, and 2 types of food are thrown into the pot. The temperature becomes (2*1 + 2*1) mod 10 + 1 = 5 degrees Celsius, and the cooking session ends.
Subtask 1 [8% of points]
N, M ≤ 1000.
Additionally, there will be no events of type 3.
Subtask 2 [17% of points]
N, M ≤ 100000.
In all events of type 1, L = H = 0.
Additionally, there will be no events of type 3.
Subtask 3 [20% of points]
N, M ≤ 100000.
X = 1 and Y = 0.
Additionally, there will be no events of type 3.
Subtask 4 [15% of points]
N, M ≤ 100000.
There will only be events of type 1.
Subtask 5 [17% of points]
N, M ≤ 100000.
There will be no events of type 3.
Subtask 6 [20% of points]
N, M ≤ 100000.
Subtask 7 [3% of points]
There are no additional constraints.
All Submissions
Best Solutions
Point Value: 40 (partial)
Time Limit: 3.00s
Memory Limit: 1024M
Added: Jul 15, 2014
Authors: FatalEagle, Alex
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
It's quiet in here...