表示言語

Problem Statement

A CUBRID HA cluster is a system consisting of N servers. The servers are numbered from 1 to N.

Jank has become the server administrator of SCSC and wants to choose some of the servers in the CUBRID HA cluster to use. Jank turns on the servers he chooses and turns off the servers he does not choose.

Jank, who rules SCSC, chooses whether each chosen server operates as a Master or as a Slave when turning it on. A Master server can process RW requests and RO requests, and a Slave server can process RO requests and SO requests. Each server can process at most one request at the same time.

If there is no Master server among the currently turned-on servers and at least one Slave server is currently turned on, the currently turned-on Slave server with the smallest number immediately becomes a Master server.

Jank, who rules SCSC, must process Q queries of the following two types in order.

• 1 i: Turn off server i. If it is already turned off, ignore this query.
• 2 a b c: a RW requests, b RO requests, and c SO requests arrive simultaneously.

The requests that arrive in a type-2 query must all be processed using only the servers that are currently turned on. Each request must be assigned to a server that can process that request, and at most one request can be assigned to each server. A request that is not assigned when the query is given cannot be processed.

When all requests have been assigned, each server processes its assigned request and discards the processed request. A server with no remaining request becomes ready to process another request again.

Find the minimum number of servers Jank, who rules SCSC, must choose initially in order to process all requests. If it is impossible to process all requests by any method, output -1 instead.

Constraints

• 1 \leq N,Q \leq 2\,000
• 1 \leq i \leq N
• 0 \leq a,b,c \leq N
• There is at least one query of the second type.
• All input values are integers.

Sample Input 1

3 4
2 2 0 0
1 1
2 0 0 1
2 1 0 1

Sample Output 1

3

表示言語

Problem Statement

Archaeologist seokgukim is studying an inscription discovered at the Sushisushi ruins.

The stone tablet currently being studied has a string S of length N engraved on it, and scholars believe that a string T of length M appears in the inscription.

Over a long period of time, some part of the originally engraved text is said to have disappeared entirely. You want to restore the string using the following method.

1. Delete a substring of length K from T. (1 \leq K < M)

2. If the string after deletion appears as a substring of S, this is called a valid restoration method.

Find the number of distinct valid restoration methods. Two valid restoration methods are considered different if at least one of the following differs: the length of the deleted substring, the position of the deleted substring, or the position where the string after deletion appears as a substring of S.

Constraints

• 1 \leq N, M \leq 200\,000
• Both S and T consist only of lowercase English letters.
• All given numbers are integers.

Sample Input 1

4 4
scsc
scpc

Sample Output 1

8

表示言語

Problem Statement

Haru_101 prepared an N \times N grid-shaped garden for SCSC. Every spring, SCSC members have a beautiful tradition of planting one flower in each cell. This year, they decided to plant sunflowers and clovers.

After all flowers were planted, Terra and Lulu looked around the garden and gave different impressions.

Terra looked down at the whole garden from a high place and said: "Looking at the whole garden, there are more cells planted with blue clovers than yellow sunflowers!"

Lulu likes taking photos, so Lulu walked around the garden and took photos of size 3 \times 3. After taking photos of every 3 \times 3 area in the garden without omission, Lulu looked at the photos and said: "Huh? In every photo I took, there are more sunflowers than clovers!"

Can you make a magical garden where, as Terra said, the whole garden has more clovers, but every photo Lulu took has more sunflowers?

Constraints

• 1 \leq T \leq 1\,000
• For each test case, 3 \leq N \leq 1\,000.
• All given numbers are integers.
• Only cases where the output does not exceed 2 MiB are given.

Sample Input 1

1
3

Sample Output 1

NO

Sample Input 2

1
4

Sample Output 2

YES
CCSC
CSSC
CSSC
CCSC

表示言語

Problem Statement

Zye is writing AI inference code to run on ARIES using Mobilint's SDK. Since Zye is a developer who is not very good at coding, the code he writes can compute only tree-shaped graphs.

Using this code, Zye wants to compute a rooted tree-shaped computation graph consisting of N tensors. The root of the tree is node 1. Node i of the tree represents a tensor of size w_i MiB.

A tensor represented by a leaf node is called an input tensor, and a tensor represented by a non-leaf node is called a result tensor. Input tensors already exist in memory in the initial state. The memory usage in the initial state is at most M MiB.

To compute the result tensor represented by node i, all tensors represented by the children of i must currently exist in memory. When computing the result tensor represented by node i, first the result tensor of size w_i MiB is allocated in memory. After the computation is finished, all tensors represented by the children of i are removed from memory.

The memory usage at a certain moment is defined as the sum of the sizes of all tensors that exist in memory at that moment.

Zye wants to choose the computation order so that the peak memory usage while computing the tensor represented by the root node is minimized. The peak memory usage is the maximum memory usage over the initial state and all moments during the computation.

The memory limit of the computer is M MiB. During the computation, the memory usage must always be at most M MiB.

Find the minimum peak memory usage needed to compute the result tensor represented by the root node.

Constraints

• 2 \leq N \leq 200\,000
• M = 16\,384
• 1 \leq w_i \leq M
• 1 \leq p_i \leq N
• The given graph is a rooted tree with root node 1.
• All input values are integers.

Sample Input 1

8 16384
6 4 5 3 2 4 3 1
1 1 2 2 4 3 3

Sample Output 1

15

In the initial state, the tensors that exist in memory are the input tensors represented by leaf nodes 5,6,7,8. Therefore, the memory usage is 2+4+3+1=10 MiB.

For example, the result tensors can be computed in the following order.

1. Compute the result tensor represented by node 4. The maximum memory usage during this step is 10+3=13 MiB.
2. Compute the result tensor represented by node 3. The maximum memory usage during this step is 9+5=14 MiB.
3. Compute the result tensor represented by node 2. The maximum memory usage during this step is 10+4=14 MiB.
4. Compute the result tensor represented by node 1. The maximum memory usage during this step is 9+6=15 MiB.

The peak memory usage for this computation order is 15 MiB. It is impossible to make the peak memory usage at most 14 MiB, so the answer is 15.

表示言語

Problem Statement

You are given N points in three-dimensional space. The coordinates of the i-th point are (x_i, y_i, z_i).

A sungjae0506 is a triangular prism that contains all the given points on its boundary or in its interior, has bases perpendicular to the z-axis, and has lateral faces perpendicular to the xy-plane.

Among all possible sungjae0506s, find the volume of the sungjae0506 that minimizes \frac{\text{volume}}{\text{surface area}}.

Constraints

• 3 \leq N \leq 100\,000
• -10^8 \leq x_i, y_i, z_i \leq 10^8
• All input values are integers.
• Let D be the distance between the farthest pair among the given N points. Only cases are given in which, even if each given point is moved to an arbitrary position within distance 10^{-6}D from its original position, the sungjae0506 minimizing \frac{\text{volume}}{\text{surface area}} exists uniquely.

Sample Input 1

6
88 848 44
-159 810 8
45 522 -21
163 793 -27
-143 706 -106
201 546 -71

Sample Output 1

15570000.000000000000000

表示言語

Problem Statement

FuriosaAI officially announced the mass production of its second-generation AI accelerator, the RNGD, this year. The RNGD is a product specialized for processing language models and multimodal models, delivering powerful computational performance while consuming minimal power.

Upon hearing the news of the RNGD chip’s mass production, Sorohue ordered N RNGD chips. Sorohue’s computer has (N+2M) slots arranged in a row, each capable of holding a single chip. Of these, 2M slots are occupied by M S-chips and M C-chips, respectively. Uniquely, the S-chips and C-chips require a single S-chip and a single C-chip to be connected via wires in order to function properly.

Sorohue decided to connect the S-chips and C-chips with wires until the ordered RNGD chips arrive. Since having too many wires crossing over empty slots makes it difficult to insert chips later, when connecting two chips with a wire, the wire must cross over at most one empty slot. It is not possible to remove and rearrange the S-chips and C-chips that are already inserted.

A string T representing the state of the slots is given. Find the number of distinct ways to connect the M pairs of chips installed in Sorohue’s computer using wires.

Two methods are considered distinct if, in one method, two chips are connected by a wire, whereas in the other method they are not.

Constraints

• 1 \le N \le 10\,000
• 1 \le M \le 10\,000
• Let T be a string consisting of N occurrences of E, M occurrences of S, and M occurrences of C.
  • The ith character of T represents the type of chip inserted into the ith slot, where E indicates an empty slot, S indicates an S-chip, and C indicates a C-chip.
• All input values are integers.

Sample Input 1

2 3
SECSCESC

Sample Output 1

4

Sample Input 2

4 1
ESEECE

Sample Output 2

0

Sample Input 3

6 11
ESSCESCCCESSCSCECCSCSESCSCES

Sample Output 3

31968

表示言語

Problem Statement

Cenix wants to fill an N \times M grid using the following six types of square tiles. There are plenty of each type of tile, and they can be rotated before placement. When placing tiles, every edge connected to a path must touch an edge connected to a path on a neighboring tile. However, not all paths need to be connected.

While filling the grid, Cenix realized that the task was too easy. Cenix now intends to fill the remaining cells using only tiles that connect one side and tiles that connect three sides.

A grid with some cells already filled with tiles is given as follows.

• The type of tile placed in the i-th row and j-th column of the grid is denoted by A_{i,j}.
  • If no tile is placed in that cell, A_{i,j} is -1.
  • If a tile is placed in that cell, A_{i,j} is the sum of 1 (if the tile is connected to the top edge), 2 (if connected to the bottom edge), 4 (if connected to the left edge), and 8 (if connected to the right edge).

Find the number of ways to fill the remaining cells using only these two types of tiles.

Constraints

• 1 \le N, M \le 500\,000
• 1 \le NM \le 500\,000
• -1 \le A_{i,j} \le 15
• All input values are integers.

Sample Input 1

3 3
10 -1 6
-1 -1 -1
9 -1 -1

Sample Output 1

2

Sample Input 2

1 3
-1 -1 -1

Sample Output 2

0

Sample Input 3

5 5
-1 -1 0 0 0
-1 -1 0 0 0
0 0 -1 0 -1
0 0 3 0 3
0 0 -1 0 -1

Sample Output 3

2

表示言語

Problem Statement

SCSC has N members. Each member has one spade card and one club card. Member i's spade card has integer S_i written on it, and their club card has integer C_i written on it.

The members of SCSC are standing in a line in the order from member 1 to member N to play the SCSC card game. Terra, the host of the game, must choose two adjacent members and make them play one of the following two duels.

• The two members each reveal the spade card with the smallest integer among their spade cards. The member who reveals the card with the larger integer wins. The losing member gives all of their club cards to the winning member and leaves.

• The two members each reveal the club card with the smallest integer among their club cards. The member who reveals the card with the larger integer wins. The losing member gives all of their spade cards to the winning member and leaves.

Any cards that the leaving member does not give to the winning member are no longer used in the game. If there were members on both sides of the leaving member, those two members become adjacent to each other.

After N-1 duels, exactly one member remains.

The last remaining member gives Terra one card with the smallest integer among their spade cards and one card with the smallest integer among their club cards, then leaves.

Let S_{\mathrm{sum}} be the sum of the integers written on all spade cards initially held by all members, and let C_{\mathrm{sum}} be the sum of the integers written on all club cards initially held by all members. Let S_f be the integer written on the spade card Terra receives at the end, and let C_f be the integer written on the club card Terra receives at the end. Then Terra's final score is (S_{\mathrm{sum}} - S_f)(C_{\mathrm{sum}} - C_f).

Terra wants the final score to be as small as possible. Find the minimum possible score Terra can obtain.

Constraints

• 1 \leq N \leq 5\,000
• 1 \leq S_i, C_i \leq 50\,000
• For all 1 \leq i < j \leq N, S_i \neq S_j and C_i \neq C_j.
• All given numbers are integers.

Sample Input 1

2
3 4
4 5

Sample Output 1

15

表示言語

Problem Statement

Terra and Lulu are playing a board game on a tree consisting of N vertices and N-1 edges. Each vertex i of the tree has a weight V_i and a multiplier W_i. The i-th edge of the tree connects vertices u_i and v_i. Initially, all multipliers W_i are 1, and vertex 1 is the root.

When a game starts, all stones currently on each vertex i are removed, and V_i \cdot W_i stones are placed on that vertex. The players take turns performing the following action.

1. Choose a non-root vertex with at least 1 stone on it.

2. Choose one or more stones on the chosen vertex and move them to its parent vertex.

The player who can no longer perform an action loses, and the other player wins. Each game starts with Terra.

Terra and Lulu are so good at the game that they found it monotonous. They decided to play Q games while performing the following two types of queries in order.

• 1 x y: For every vertex i on the shortest path between vertices x and y, change its multiplier W_i to 1 - W_i. In other words, 0 changes to 1, and 1 changes to 0.

• 2 z: Change the root of the tree to vertex z. If vertex z is already the root of the tree, nothing happens.

Each time a query is performed, Terra and Lulu start a new game from the beginning. For each of the Q games, determine who wins if both players play optimally. The effects of all queries are cumulative.

Constraints

• 2 \leq N \leq 300\,000
• 1 \leq Q \leq 500\,000
• 1 \leq V_i \leq 10^9
• 1 \leq u_i, v_i \leq N
• 1 \leq x, y, z \leq N
• u_i \ne v_i
• All given numbers are integers.
• The given graph is a tree.

Sample Input 1

4 4
10 1 2 3
1 2
1 3
1 4
2 1
1 2 3
2 2
1 1 1

Sample Output 1

Lulu
Terra
Lulu
Terra

表示言語

Problem Statement

ChannelTalk, an all-in-one AI messenger that facilitates real-time communication with customers, offers a workflow feature that allows anyone to easily create chatbots. Using ChannelTalk Workflow, you can combine triggers and actions like building blocks based on the customer and the situation to automate the entire process from the start to the end of a consultation. Additionally, frequently used functions can be created as modules and reused multiple times.

Ino intends to build a chatbot using ChannelTalk Workflow to handle N different types of questions. Each question is assigned a unique number from 1 to N.

Ino wants to add M modules to the workflow and number them from 0 to M-1 in the order they are added. Since Ino cannot manage too many modules, at most 2\,048 modules can be used.

When question x is entered, module i operates as follows.

• If x = i, it answers the question and ends the consultation.
• If x \neq i, it enters question x to module L_i if x \le F_i, and module G_i if x \gt F_i.

When a question is received, it is first input to module 0, and executing each module takes 1 second. That is, the time taken to process question i is equal to the total number of modules passed through, including module 0 and module i, until the consultation ends. If the same module is passed through multiple times, it is counted as many times as it was passed through.

Ino wants to ensure that the consultation ends in exactly K seconds regardless of which question from 1 to N is asked. Given the number of question types N and the ending time K, choose the number of modules M and the values of F_i, L_i, and G_i for each module so that the consultation always ends exactly at K seconds using at most 2\,048 modules. Note that M does not need to be minimized.

Constraints

• 2 \le K \le N \le 1\,000
• All input values are integers.

Sample Input 1

6 6

Sample Output 1

11
1 7 1
2 7 2
3 7 3
4 7 4
5 5 6
4 0 0
5 0 0
3 8 4
2 9 3
1 10 2
0 0 1

表示言語

Problem Statement

Coshaman bought a roll cake of length L for the SCSC clubroom. The roll cake consists of L consecutive pieces of length 1, and the preference value of the i-th piece from the left is V_i.

Lulu wants to store the roll cake in a refrigerator. However, the clubroom refrigerator cannot store a roll cake of length greater than K, so Lulu decided to cut the roll cake into pieces of length at most K. Since cutting through a piece would make it ugly, Lulu must cut only between adjacent pieces.

When a roll cake is put into the refrigerator, only the end piece is visible from outside. Since the roll cakes must be put in with a fixed orientation, only the rightmost piece of each cut roll cake is visible. Lulu likes pretty things, so Lulu defines the beauty of storage as the sum of the preference values of the visible pieces.

Cutting a roll cake is hard work, so Lulu wants to store it with large beauty of storage while using little effort. When cutting a roll cake of length s into two roll cakes of lengths x and y (x+y=s), the required effort is x \times y. If several cuts are made, the effort required for the storage is the sum of the effort required for each cut.

Given L, K, and the preference values of each roll cake piece, find the maximum possible value of (\text{beauty of storage}) - (\text{effort required for storage}).

Constraints

• 1 \leq K \leq L \leq 1\,000\,000
• 0 \leq V_i \leq 10^9
• All given numbers are integers.

Sample Input 1

4 4
1 2 3 4

Sample Output 1

4

Sample Input 2

3 1
1 2 3

Sample Output 2

3

表示言語

Problem Statement

Lulu is actually a genius magician. After a long period of research, Lulu developed a secret magic of her own using a magic circle.

The magic circle Lulu uses is a tree structure consisting of N spells and N-1 connections. The spells are numbered in order from 1 to N, and Lulu can strengthen each spell. The i-th connection of the magic circle means that spell a_i and spell b_i are directly connected.

Initially, the power of every spell is 0. When Lulu strengthens spell r by w, the power W_r of spell r increases by w.

Lulu can cast magic by choosing two spells u and v in the magic circle. When Lulu casts magic, every spell in the magic circle interacts with the set P(u,v) of vertices on the unique simple path connecting u and v. The final power of the magic Lulu casts can be calculated by the following formula. Here, d(a,b) is the number of edges on the unique simple path connecting a and b.

The genius magician Lulu wants to learn magic by performing the following two types of actions in order, Q times in total.

• 1 v w: Increase the power of spell v by w.

• 2 u v: Choose spells u and v and cast magic.

For each action of type 2, compute the final power of the cast magic modulo 998\,244\,353.

Constraints

• 1 \leq N, Q \leq 200\,000
• 1 \leq a_i, b_i \leq N
• a_i \ne b_i
• The given magic circle is a tree.
• In an action of the form 1 v w, 1 \leq v \leq N and 1 \leq w \leq 10^9.
• In an action of the form 2 u v, 1 \leq u, v \leq N.
• All given numbers are integers.

Sample Input 1

4 3
1 2
2 3
3 4
1 2 5
1 4 3
2 1 4

Sample Output 1

38