시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 1024 MB853100.000%

문제

For two arrays of integers $A$ of size $N$ and $B$ of size $M$, we define a grid $G(A, B)$ of size $N \times M$, where cell $(i,\, j)$ is colored black if $0 \le A_i + B_j$ and white otherwise.

We also define $F(A, B)$ as the number of black rectangles inside $G(A, B)$, where each cell of $G(A, B)$ is either entirely included in or disjoint with the rectangle.

In other words, $F(A, B)$ is equal to the number of tuples $(l_1,\, r_1,\, l_2,\, r_2)$ such that $1 \le l_1 \le r_1 \le N$, $1 \le l_2 \le r_2 \le M$ and each cell $(i,\,  j)$ in $G(A, B)$ is colored black for all $i$, $j$ such that $l_1 \le i \le r_1$, $l_2 \le j \le r_2$.

Initially, only $A_1$ and $B_1$ are given.

Then, you should process following $Q$ queries:

  • 0 $v$: append $v$ to current array $A$.
  • 1 $v$: append $v$ to current array $A$. Then, print $F(A, B)\bmod 998\,244\,353$.
  • 2 $v$: append $v$ to current array $B$.
  • 3 $v$: append $v$ to current array $B$. Then, print $F(A, B)\bmod 998\,244\,353$.

입력

The first line contains one integer $Q$.

The second line contains two space-separated integers, $A_1$ and $B_1$.

Each of the following $Q$ lines contains two space-separated integers denoting the queries in the described form.

출력

For each query of types 1 and 3, output a single integer denoting the answer to that query. Each answer should go on its own line.

제한

Let $N$ be the size of array $A$ after processing all queries, and $M$ be the size of array $B$ after processing all queries.

  • $1 \le N \le 250\,000$
  • $1 \le M \le 250\,000$
  • $1 \le Q = N + M - 2$
  • $-10^9 \le A_{i} \le 10^9$ $(1 \le i \le N)$
  • $-10^9 \le B_{i} \le 10^9$ $(1 \le i \le M)$
  • The last query has a type of 1 or 3.

서브태스크 1 (30점)

This subtask has additional constraints:

  • $N \le 2\,500$
  • $M \le 2\,500$

서브태스크 2 (15점)

This subtask has an additional constraint:

  • Every query except the last one has type of 0 or 2.

서브태스크 3 (55점)

This subtask has no additional constraints.

예제 입력 1

4
-4 -3
0 -5
2 2
0 3
3 -5

예제 출력 1

3

예제 입력 2

8
-187121777 648583176
0 536185451
1 77324177
2 -543947071
1 -495948203
2 809620127
2 918209957
3 -724806401
1 30094601

예제 출력 2

6
10
40
60

출처

University > KAIST > 2022 KAIST RUN Spring Contest G번

채점 및 기타 정보

  • 예제는 채점하지 않는다.