No.3396 ChRisTmas memory
レベル :
/ AI推定難易度 : 2150
/ 実行時間制限 : 1ケース 4.000秒 / メモリ制限
: 80 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 :
KumaTachiRen
/ テスター :
tko919
タグ : / 解いたユーザー数 20
作問者 :
tko919
問題文最終更新日: 2025-12-02 01:02:56
English (AI translation)
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
Advent Calendar Contest 2025
(順位表)
の他の問題:
Note
The time and memory limits are set strictly relative to the constraints. The execution time and memory usage of submissions implementing the intended solution (about 40 ~ 60 lines / 1,000 ~ 1,300 bytes) are as follows.
- C++: 1,145 ms / 7,720 KB
- C#(csc): 1,757 ms / 28,800 KB
- PyPy: 1,723 ms / 77,800 KB
Problem Statement
There are integer sequences $M,R$, both initially empty. Process $Q$ queries. Each query is one of the following.
-
Append query
1 m r: Append $m$ to the end of $M$ and $r$ to the end of $R$. -
Delete query
2 k: Delete the last $k$ elements from each of $M,R$. -
Output query
3 m: Let $M=(M_1,M_2,\dots,M_n),R=(R_1,R_2,\dots,R_n)$. If there exists a non-negative integer $X$ such that $X\bmod M_i=R_i$ for $i=1,2,\dots,n$, output the remainder when the smallest such $X$ is divided by $m$ (in particular, if $M,R$ are empty, output $0$). If no such $X$ exists, output $-1$.
Input
$Q$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\ \vdots$
$\mathrm{query}_Q$
- $Q$ is an integer between $1$ and $10^4$, inclusive.
- $\mathrm{query}_i$ represents the $i$-th query and is in one of the following formats.
1 $m$ $r$
- $m,r$ are integers satisfying $0\leq r\lt m\leq 10^9$.
2 $k$
- $k$ is a positive integer.
- When this query is given, the lengths of $M,R$ are both at least $k$.
3 $m$
- $m$ is an integer between $1$ and $10^9$, inclusive.
Output
Output the answers to the queries, separated by newlines.
Sample
Sample 1
Input
10 1 3 2 1 5 3 1 7 2 3 100 1 10 7 3 1 2 2 1 10 8 1 21 5 3 1225
Output
23 -1 68
- The conditions for the first output query are $X\bmod 3=2,X\bmod 5=3,X\bmod 7=2$, and the smallest non-negative integer $X$ satisfying them is $X=23$.
- The conditions for the second output query are $X\bmod 3=2,X\bmod 5=3,X\bmod 7=2,X\bmod 10=7$, and no non-negative integer $X$ satisfies them.
- The conditions for the third output query are $X\bmod 3=2,X\bmod 5=3,X\bmod 10=8,X\bmod 21=5$, and the smallest non-negative integer $X$ satisfying them is $X=68$.
Sample 2
Input
21 3 843957008 1 472606293 274537750 3 64772011 1 193496841 55561237 1 451893048 386182462 3 55362928 2 2 1 809555949 430585126 1 332038764 226085506 1 382738349 129580124 3 539680759 1 231823672 217838911 1 306480274 85596938 3 179792542 2 3 1 331955943 153336259 1 252027932 57148750 1 804119517 717446500 3 413073477 3 401206962 3 163951831
Output
0 15449706 42497622 132215773 -1 299588848 78602104 132982172
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。