問題一覧 > 通常問題

No.3396 ChRisTmas memory

レベル : / AI推定難易度 : 2150 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 80 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 20
作問者 : KumaTachiRen / テスター : tko919
お気に入りにしたユーザー ProblemId : 12767 / 自分の提出
問題文最終更新日: 2025-12-02 01:02:56
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
The memory limit is especially severe for interpreted languages such as Python. Please be aware of this.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。