DMOPC '19 Contest 4 P6 - little_prince's Specialty Tea House

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 2.5s
Memory limit: 256M

Problem type

little_prince is opening a specialty tea house! One of his famous dishes is taiyaki, which is typically cooked in small fish-shaped molds. little_prince has N such molds lined up in a row. He knows that the batter inside the i-th taiyaki still needs to cook for t_i more seconds to be done. As running a specialty tea house is a lot of work, he wants you to help him answer Q queries, each of which is one of the following types:

  • 1 x which means to print the amount of time the i-th taiyaki still needs to be cooked.

  • 2 x y t which means that little_prince considers cooking the pans x, x+1, \dots, y for t seconds. If it would cause one of the taiyaki to overcook (overcooking means that t > t_i, where x \le i \le y), he ignores this instruction. Otherwise, he cooks each taiyaki in the range for t seconds.

  • 3 x y t which means that little_prince deems that the taiyaki in pans x, x+1, \dots, y are not up to standard. He pours new batter into the pans starting from left to right at a rate of one pan per second while the pans are heating. This means that the cook times of the pans becomes t_i=t-y+i for x \le i \le y as the earlier pans get cooked a little when little_prince is pouring in the batter for the later pans. It is guaranteed that t-y+x \ge 0.

  • 4 x y which means that little_prince reduces the cook times of each taiyaki in pans x, x+1, \dots, y to the floor of the square root of its original cook time. That is t_i=\left\lfloor \sqrt{t_i} \right\rfloor for x \le i \le y.


In all subtasks,
1 \le N \le 100\,000
1 \le Q \le 500\,000
1 \le x \le y \le N
1 \le t_i, t \le 10^{18}

Subtask 1 [10%]

1 \le N, Q \le 2\,000

Subtask 2 [20%]

There are no type 3 or type 4 operations.

Subtask 3 [20%]

There are no type 3 operations.

Subtask 4 [50%]

No additional constraints.

Input Specification

The first line contains two integers, N and Q.
The second line contains N integers, t_1, t_2, \dots, t_N, the initial cook times.
The next Q lines each contain a query, in the format as described above.

Output Specification

Output one integer on a separate line for each type 1 query.

Sample Input

5 8
1 3 1 7 6
2 3 5 3
4 1 3
1 3
3 2 4 4
1 3
4 1 5
2 1 4 1
1 3

Sample Output


Explanation for Sample Output

The first operation cannot be completed as it would cause the third taiyaki to overcook. Therefore, the array is 1 3 1 7 6.
After the second operation, the array is 1 1 1 7 6.
After the fourth operation, the array is 1 2 3 4 6.
After the sixth operation, the array is 1 1 1 2 2.
After the seventh operation, the array is 0 0 0 1 2.


  • 2
    Narcariel  commented on Jan. 17, 2020, 9:43 a.m.

    Do you think you could add an extra sample input/output please :) ?