Mock CCC '20 S4 - Valentine's Day Shopping

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Valentine's day is coming up, and Larry is shopping for a gift to impress his crush!

In the gifts store, there are N gifts lined up in a row, each with sizes s_1, s_2, \dots, s_N respectively, and Larry only has boxes of size B (a box of size B can fit any number of gifts as long as their total size is \le B). As he is very stingy and wants to use as few boxes as possible, he wants you to help him minimize the number of boxes. Additionally, Q times during his shopping trip, one of the two following events will happen:

  • Q l_i r_i: Larry will look at the subarray of gifts s_{l_i}, s_{l_i+1}, \dots, s_{r_i} and consider them for purchase (he doesn't actually buy them). He would like to group the gifts into x contiguous groups such that the sum of all gift sizes in each group is \le B. Your job is to tell him the minimum possible x, or to tell him -1 if it's impossible.
  • U x_i v_i: The gift at index x undergoes spontaneous molecular restructuring and changes size to v.


1 \le N, Q \le 10^5

1 \le l_i \le r_i \le N

1 \le x_i \le N

1 \le B, s_i, v_i \le 10^9

For 3 of 15 available marks, 1 \le N, Q \le 100.

Input Specification

The first line of input will contain N, Q, and B.

The second line of input will contain the initial values of s_1, s_2, \dots, s_N.

The next Q lines will contain an event in one of the above specified forms.

Output Specification

Output the answer to each type Q event, each on its own line.

Sample Input

8 6 4
3 2 3 3 3 1 1 99
Q 1 3
U 2 1
Q 1 3
Q 4 6
Q 1 7
Q 1 8

Sample Output


Sample Explanation

Here are the groups for each query:

  • [[3], [2], [3]] for Q 1 3
  • [[3, 1], [3]] for Q 1 3 (second time)
  • [[3], [3, 1]] for Q 4 6
  • [[3, 1], [3], [3], [3, 1], [1]] for Q 1 7
  • Q 1 8 is impossible


There are no comments at the moment.