問題一覧 > 教育的問題

No.2395 Range Quadratic Transformation, Point Get

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 82
作問者 : 👑 p-adic / テスター : ecottea hiro1729
お気に入りにしたユーザー ProblemId : 9427 / 自分の提出
問題文最終更新日: 2023-07-26 16:09:47
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 399 (順位表) の他の問題:

Problem Statement

You are given $3$ positive integers $N, B, Q$ and $Q$ queries (described below) as input.

　

For a sequence $a$ of non-negative integers of length $N$ and a positive integer $i$ not exceeding $N$, $a_i$ denotes the $i$-th element of $a$.

Initially, sequences $X, Y, Z$ of non-negative integers of length $N$ are given, each consisting only of $1$.

Each query is a triple $(L,M,R)$ of integers $L, M, R$ satisfying $1 \leq L \leq M \leq R \leq N$.

A query $(L,M,R)$ is processed as follows:

  1. First, for each positive integer $i$ satisfying $L \leq i \leq R$, update $X$ by replacing the $i$-th element of $X$ with $X_i + 1$.
  2. Next, for each positive integer $i$ satisfying $L \leq i \leq R$, update $Y$ by replacing the $i$-th element of $Y$ with $3Y_i + 2X_i Z_i$.
  3. Then, for each positive integer $i$ satisfying $L \leq i \leq R$, update $Z$ by replacing the $i$-th element of $Z$ with $3Z_i$.
  4. Finally, compute the remainders of $X_M, Y_M, Z_M$ when each is divided by $B$. (Hereafter, these values are called the answer to this query.)

Note that in step 2, $X_i$ refers to $X$ after the update in step 1. Also note that in step 4, $X_M, Y_M, Z_M$ refer to $X, Y, Z$ after the updates in steps 1, 2, and 3.

　

Process the $Q$ queries in the given order.

Input

The input is given from standard input in $1 + Q$ lines in the following format:

  • The $1$-st line contains $N, B, Q$ separated by single-byte spaces.
  • For each positive integer $q$ not exceeding $Q$, letting $(L_q,M_q,R_q)$ be the $q$-th query, line $1 + q$ contains $L_q, M_q, R_q$ separated by single-byte spaces.
$N$ $B$ $Q$
$L_1$ $M_1$ $R_1$
$\vdots$
$L_Q$ $M_Q$ $R_Q$

Constraints

The input satisfies the following constraints:

  • $N$ is an integer satisfying $1 \leq N \leq 10^5$.
  • $B$ is an integer satisfying $1 \leq B \leq 10^9$.
  • $Q$ is an integer satisfying $1 \leq Q \leq 10^5$.
  • For any positive integer $q$ not exceeding $Q$, $L_q, M_q, R_q$ are integers satisfying $1 \leq L_q \leq M_q \leq R_q \leq N$.

Output

For each positive integer $q$ not exceeding $Q$, output the answer to the $q$-th query on the $q$-th line, separated by single-byte spaces.

Print a newline at the end.

Sample

Sample 1
Input
1 1 1
1 1 1
Output
0 0 0

Initially, $X, Y, Z$ are all given as $(1)$.

By the query $(L_1,M_1,R_1) = (1,1,1)$, first $X$ is replaced with

$\displaystyle (X_1 + 1) = (1+1) = (2) $

next $Y$ is replaced with

$\displaystyle (3Y_1 + 2X_1 Z_1) = (3 \times 1 + 2 \times 2 \times 1) = (7) $

and then $Z$ is replaced with

$\displaystyle (3Z_1) = (3 \times 1) = (3) $

For the updated $(X,Y,Z)$, we have $(X_M,Y_M,Z_M) = (X_1,Y_1,Z_1) = (2,7,3)$, and the remainders of $2,7,3$ when divided by $B = 1$ are $0,0,0$, respectively.

Since $Q = 1$ in this case, all processing ends here.

Sample 2
Input
2 2 1
1 1 1
Output
0 1 1

Initially, $X, Y, Z$ are all given as $(1,1)$.

By the query $(L_1,M_1,R_1) = (1,1,1)$, first $X$ is replaced with

$\displaystyle (X_1 + 1, X_2) = (1+1,1) = (2,1) $

next $Y$ is replaced with

$\displaystyle (3Y_1 + 2X_1 Z_1, Y_2) = (3 \times 1 + 2 \times 2 \times 1, 1) = (7,1) $

and then $Z$ is replaced with

$\displaystyle (3Z_1, Z_2) = (3 \times 1, 1) = (3,1) $

For the updated $(X,Y,Z)$, we have $(X_M,Y_M,Z_M) = (X_1,Y_1,Z_1) = (2,7,3)$, and the remainders of $2,7,3$ when divided by $B = 2$ are $0,1,1$, respectively.

Since $Q = 1$ in this case, all processing ends here.

Sample 3
Input
2 4 2
1 1 2
2 2 2
Output
2 3 3
3 3 1

Initially, $X, Y, Z$ are all given as $(1,1)$.

By the query $(L_1,M_1,R_1) = (1,1,2)$, first $X$ is replaced with

$\displaystyle (X_1 + 1, X_2 + 1) = (1+1,1+1) = (2,2) $

next $Y$ is replaced with

$\displaystyle (3Y_1 + 2X_1 Z_1, 3Y_2 + 2X_2 Z_2) = (3 \times 1 + 2 \times 2 \times 1, 3 \times 1 + 2 \times 2 \times 1) = (7,7) $

and then $Z$ is replaced with

$\displaystyle (3Z_1, 3Z_2) = (3 \times 1, 3 \times 1) = (3,3) $

For the updated $(X,Y,Z)$, we have $(X_M,Y_M,Z_M) = (X_1,Y_1,Z_1) = (2,7,3)$, and the remainders of $2,7,3$ when divided by $B = 4$ are $2,3,3$, respectively.

By the $2$-nd query $(L_2,M_2,R_2) = (2,2,2)$, first $X$ is replaced with

$\displaystyle (X_1,X_2 + 1) = (2,2+1) = (2,3) $

next $Y$ is replaced with

$\displaystyle (Y_1,3Y_2 + 2X_2 Z_2) = (7,3 \times 7 + 2 \times 3 \times 3) = (7,39) $

and then $Z$ is replaced with

$\displaystyle (Z_1,3Z_2) = (3,3 \times 3) = (3,9) $

For the updated $(X,Y,Z)$, we have $(X_M,Y_M,Z_M) = (X_2,Y_2,Z_2) = (3,39,9)$, and the remainders of $3,39,9$ when divided by $B = 4$ are $3,3,1$, respectively.

Since $Q = 2$ in this case, all processing ends here.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。