No.3492 Range Power Addition, Point Query
タグ : / 解いたユーザー数 30
作問者 : 👑
p-adic
Note
The execution time limit for this problem is 4000[ms]. Since the time limit is tight, using a fast language and implementation is recommended.
For reference, the execution time of the writer's solution is 577[ms] in c++, 1596[ms] in PyPy3, and over 10000[ms] in Python3, that is, TLE.
Problem Statement
At the beginning of the input, $3$ positive integers $N, B, Q$ are given.
There is a sequence $A$ of non-negative integers of length $N$, which initially has only $0$ as its elements.
Update $A$ by processing the $Q$ queries described below in the given order.
Each query is a tuple $(L,M,R,C,D)$ of $3$ integers $L, M, R$ satisfying $1 \leq L \leq M \leq R \leq N$ and $2$ non-negative integers $C, D$.
A query $(L,M,R,C,D)$ is processed as follows:
- First, for each positive integer $i$ satisfying $L \leq i \leq R$, update $A$ by replacing the $i$-th element of $A$ with $A_i + (i+C)^D$.
- Next, find the remainder when $A_M$ of the updated $A$ is divided by $B$. (Hereafter, this value is called the answer to this query.)
Here, for each positive integer $i$ not greater than $N$, $A_i$ denotes the $i$-th element of $A$.
Input
For each positive integer $q$ not greater than $Q$, let $(L_q,M_q,R_q,C_q,D_q)$ be the $q$-th query.
Then, the input is given from standard input in $1 + Q$ lines in the following format:
- Line $1$ contains $N, B, Q$, separated by single spaces.
- For each positive integer $q$ not greater than $Q$, line $1+q$ contains the components $L_q,M_q,R_q,C_q,D_q$, separated by single spaces.
$N$ $B$ $Q$ $L_1$ $M_1$ $R_1$ $C_1$ $D_1$ $\vdots$ $L_Q$ $M_Q$ $R_Q$ $C_Q$ $D_Q$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $1 \leq N \leq 10^4$
- $B$ is an integer satisfying $1 \leq B \leq 10^9$
- $Q$ is an integer satisfying $1 \leq Q \leq 10^4$
- For any positive integer $q$ not greater than $Q$,
- $L_q,M_q,R_q$ are integers satisfying $1 \leq L_q \leq M_q \leq R_q \leq N$
- $C_q$ is an integer satisfying $0 \leq C_q \leq 10^{18}$
- $D_q$ is an integer satisfying $0 \leq D_q \leq 10^2$
Output
For each positive integer $q$ not greater than $Q$, print the answer to the $q$-th query on line $q$.
Print a newline at the end.
Sample
Sample 1
Input
1 2 1 1 1 1 2 0
Output
1
Initially, the sequence $A$ of non-negative integers of length $N = 1$ is given as $(0)$.
By the $1$-st query $(L_1,M_1,R_1,C_1,D_1) = (1,1,1,2,0)$, first, $A$ is replaced with
$\displaystyle (A_1 + (1 + C_1)^{D_1}) = (0 + (1 + 2)^0) = (1) $
. Therefore, $A_{M_1} = A_1$ of the updated $A$ is $1$, and the remainder when $1$ is divided by $B = 2$ is $1$.
Since $Q = 1$ in this case, all processing is now finished.
Sample 2
Input
2 3 1 1 2 2 1 1
Output
0
Initially, the sequence $A$ of non-negative integers of length $N = 2$ is given as $(0,0)$.
By the $1$-st query $(L_1,M_1,R_1,C_1,D_1) = (1,2,2,1,1)$, first, $A$ is replaced with
$\displaystyle (A_1 + (1 + C_1)^{D_1},A_2 + (2 + C_1)^{D_1}) = (0 + (1 + 1)^1,0 + (2 + 1)^1) = (2,3) $
. Therefore, $A_{M_1} = A_2$ of the updated $A$ is $3$, and the remainder when $3$ is divided by $B = 3$ is $0$.
Since $Q = 1$ in this case, all processing is now finished.
Sample 3
Input
3 4 2 1 1 2 0 2 2 2 3 2 1
Output
1 0
Initially, the sequence $A$ of non-negative integers of length $N = 3$ is given as $(0,0,0)$.
By the $1$-st query $(L_1,M_1,R_1,C_1,D_1) = (1,1,2,0,2)$, first, $A$ is replaced with
$\displaystyle (A_1 + (1 + C_1)^{D_1},A_2 + (2 + C_1)^{D_1},A_3) = (0 + (1 + 0)^2,0 + (2 + 0)^2,0) = (1,4,0) $
. Therefore, $A_{M_1} = A_1$ of the updated $A$ is $1$, and the remainder when $1$ is divided by $B = 4$ is $1$.
By the $2$-nd query $(L_2,M_2,R_2,C_2,D_2) = (2,2,3,2,1)$, first, $A$ is replaced with
$\displaystyle (A_1,A_2 + (2 + C_2)^{D_2},A_3 + (3 + C_2)^{D_2}) = (1,4 + (2 + 2)^1,0 + (3 + 2)^1) = (1,8,5) $
. Therefore, $A_{M_2} = A_2$ of the updated $A$ is $8$, and the remainder when $8$ is divided by $B = 4$ is $0$.
Since $Q = 2$ in this case, all processing is now finished.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。