Back To School '18: Function Maximization

View as PDF

Submit solution



Points: 25 (partial)
Time limit: 3.0s
Java 6.0s
Turing 25.0s
Memory limit: 1G
Java 1G
Turing 1G
Authors:

Problem types

Evan somehow found an array, a, consisting of N integers in the range [K, K+5\ 000] on the ground. Looking at it, he came up with a problem. However, he has no clue how to solve it. After asking all his friends, no one knew how to solve it, so he comes to you, asking for help.

Evan gives you the following function:

\displaystyle 
f(x) = \begin{cases} x & \text{if }(x-1)!+1 \equiv 0 \pmod x\\ -1 & \text{if } (x-1)!+1 \not\equiv 0 \pmod x \end{cases}

where ! denotes the factorial operation. In other words, the function returns x if (x-1)!+1 is divisible by x, and -1 otherwise.

Evan will give you Q queries:

  • 1 l r Print the maximum value of f(k) for all elements k in the subarray [l, r]\ (1 \le l \le r \le N).
  • 2 l r v Add v\ (1 \le |v| \le 5\ 000) to all elements in the subarray [l, r]\ (1 \le l \le r \le N).

Input Specification

The first line will contain 3 integers, N, Q, K\ (1 \le N \le 10^5, 1 \le Q \le 5 \times 10^4, 2 \le K \le 10^{14}).

The second line will contain N integers, a_1, a_2, \ldots, a_N\ (K \le a_i \le K+5\ 000), the initial array.

The next Q lines will each contain a valid query as defined above.

It is guaranteed that at any point in time, all elements of the array will be in the range [K,K+5\ 000].

Output Specification

For every type 1 query, output the maximum value of f(k) for all elements k in the subarray [l, r] on its own line.

Subtasks

Subtask 1 [10%]

N, Q \le 100

K = 2

Subtask 2 [30%]

K \le 10^5

Subtask 3 [60%]

No further constraints.

Sample Input

9 9 2
2 3 5 6 8 10 7 11 16
1 1 5
2 1 5 1
1 1 5
1 4 5
1 6 8
1 9 9
2 6 9 -3
1 6 8
1 9 9

Sample Output

5
7
7
11
-1
7
13

Comments

There are no comments at the moment.