Sanjar Bidaibek

Есеп №1. (Сиқырлы матрица)

Ограничение по времени:

2 seconds

Ограничение по памяти:

256 megabytes

Жас сиқыршы Асхат жаңа сиқырдың жаңа түрін ойлап тапты — енді ол кез келген матрицаны оның префикс қосындысымен ауыстыра алады!
Жаңадан меңгерген қабілетіне сенімді болу үшін, ол біраз жаттығамын деп шешті. Ол өлшемдері шексіз үлкен, барлық элементтері $1$ саны болатын матрицаны алып, сол матрицаға өте көп рет жоғарыда айтылған сиқырды қолданды.
Бұл есепте сіз өзіңіздің бағдарламалау қабілетіңіз сиқырдан еш кем емес екенін дәлелдеу. Сізге саны өте көп сұраулар беріледі. Солардың әрқайсысына бастапқы матрицаға жоғарыда келтірілген сиқырды $k$ рет қолданғаннан кейін, матрицаның $i$-жолындағы және $j$-қатарындағы тұрған санның мәнін анықтаңыз. Ол сан өте үлкен болуы мүмкін болғандықтан 1000000007-ге бөлгендегі қалдығын шығарыңыз.

Формат входного файла

Бірінші жолда жалғыз оң сан $Q \; (1 <= Q <= 10^5)$ берілген — сіздің бағдарламаңызға берілетін сұраулардың саны.
Келесі берілген $Q$ жолдың әрқайсысы бағдарламаға келген кезекті сұрауды үш сан арқылы сипаттайды: сәйкесінше жол нөмірі $i$, қатар нөмірі $j$ және сиқырдың неше рет қолданылғанын көрсететін сан $k$ $(1 <= i, j, k <= 10^5)$.

Формат выходного файла

Келесі $Q$ жолдың әрқайсысында бір саннан шығарыңыз — сиқырды $k$ рет қолданғаннан кейін, матрицаның $i$-жолындағы және $j$-қатарындағы тұрған санның мәннің 1000000007-ге бөлгендегі қалдығы.

Система оценки

1-бөлім (10 ұпай) — $1 <= Q <= 10, 1 <= i, j, k <= 100$ 2-бөлім (10 ұпай) — $1 <= i, j, k <= 100$ \par 3-бөлім (10 ұпай) — $1 <= i, j, k <= 10^3$ \par 4-бөлім (10 ұпай) — $i = 1$ немесе $j = 1$ \par 5-бөлім (10 ұпай) — $k = 1$ \par 6-бөлім (50 ұпай) — қосымша шарттарсыз.

Примеры:

\exmpfile{example.01}{example.01.a}% \exmpfile{example.02}{example.02.a}%

Замечание

   Еске сала кетсек, матрица — бүтін сандардан тұратын екі өлшемді массив (басқаша айтқанда, кесте). Мысалы, өлшемі 3x4 болатын матрица: \begin{center} \begin{tabular}{|c|c|c|c|} \hline 1 & 2 & 3 & 4\\ \hline 4 & 7 & 0 & -2\\ \hline 5 & 9 & 2 & 6\\ \hline \end{tabular} \end{center}
   Префикс қосынды — кез келген элементі осы сәйкес келетін тормен және қарама-қарсы бұрышы $(1, 1)$ торымен шектелген тіктөртбұрышағы сандардың қосындысы болатын матрица. Басқаша айтқанда, $A$ матрицасының префикс қосындысы деп $B$ матрицасын алсақ, кез келген $i > 0, \; j > 0$ үшін келесі шарт орындалуы қажет: \[B_{i, j} = A_{i, j} + B_{i - 1, j} + B_{i, j - 1} - B_{i - 1, j - 1}\]
   $B$ матрицасының $i = 0$ және $j = 0$ болатын ұяшықтарында нөл жазылған.
   Келесі матрица үшін \begin{center} \begin{tabular}{|c|c|c|c|} \hline 1 & 2 & 0 & 1\\ \hline 4 & 1 & 5 & 9\\ \hline 3 & 2 & 6 & 1\\ \hline 0 & 7 & 2 & 4\\ \hline \end{tabular} \end{center}
   Префикс қосынды матрица төмендегідей болады: \begin{center} \begin{tabular}{|c|c|c|c|} \hline 1 & 3 & 3 & 4\\ \hline 5 & 8 & 13 & 23\\ \hline 8 & 13 & 24 & 35\\ \hline 8 & 20 & 33 & 48\\ \hline \end{tabular} \end{center} ( Sanjar Bidaibek )
комментарий/решение(6) олимпиада

Есеп №2.

Задача A. Қояндар

Ограничение по времени:

2 seconds

Ограничение по памяти:

256 megabytes

Айбарда $K$ бөлімнен тұратын бақша бар. Бақшада $n$ қояндар тұрады. Әрбір қоян бақшаның бір бөлімінде орналасқан. Кейде қояндар көршілес бөлімдерге өтуі мүмкін. Сондай-ақ, кейде Айбар оларды тамақтандыру үшін кейбір бөлімдердегі қояндардың санын білу керек. Айбарға $q$ сұраныстар берілген. Олар келесі түрде болады:

$x$-шi нөмірдегі қоян $(1 <= x <= n)$ бір бөлімге солға немесе оңға көшті. Бұл жағдайда қоян бақшадан тыс шықпайтынына кепілдік беріледі
$l$-ден $r$-ге дейінгі $(1 <= l <= r <= K)$ бөлімдердегі қояндардың санын табу керек.

Формат входного файла

Бірінші жолда екі сан берілген - $n$ және $K$. \\ Екінші жолда $n$ сандар - әрбір қоянның бастапқыда орналасқан бөлімнің нөмірі көрсетілген.\\ Содан кейін жеке жолда сұраныстардың санын сипаттайтын $q$ саны берілген. Келесі $q$ жолдарда сұраныстардың сипаттаулары берілген. Сұраулар келесі түрде беріледі:

$\texttt{L } x$ - $x$-ші қоян сол жақта орналасқан бөлімге көшті
$\texttt{R } x$ - $x$-ші қоян оң жақта орналасқан бөлімге көшті
$\texttt{G } l\; r$ - $l$-ден бастап $r$-ге дейінгі аралықтағы қояндардың санын санап, шығару.

Формат выходного файла

Үшінші типтегі әрбір сұранысқа бөлек жолда бір сан — сұраныстың жауабын шығарыңыз.

Система оценки

Бұл есеп $3$ бөлімнен тұрады:

$1 <= n, K, q <= 1000$. $20$ баллға бағаланады.
$1 <= n, K, q <= 5 * 10^5$. Қояндардың көшу сұраулары жоқ. $20$ баллға бағаланады.
$1 <= n, K, q <= 5 * 10^5$. $60$ баллға бағаланады.

Пример:

Вход

Ответ

1
3

( Sanjar Bidaibek )
комментарий/решение(12) олимпиада