Korone just bought $$$2 \leq N \leq 3,000$$$ Yubi's, which is one of her favorite snacks. The snacks are labelled $$$0,1,...N-1$$$. To stop herself from eating it all at once, she decided to bury the snacks in her backyard. She will bury each snack at some non-negative integer coordinates $$$(X, Y)$$$ where $$$0 \leq X \leq 100,000$$$ and $$$0 \leq Y \leq 100,000$$$. Multiple Yubi's can be buried at the same coordinate.
After burying the snacks, she thought that it is only obvious to consider the Sorted Pairwise Distance List (SPDL), which is just the list of all distances between any distinct unordered pair of snacks, sorted in non-decreasing order. Here we define the distance between a pair of points $$$P=(X_P,Y_P)$$$ and $$$Q=(X_Q,Y_Q)$$$ as $$$(X_P-X_Q)^2 + (Y_P-Y_Q)^2$$$. Unless stated otherwise, any mention of distance will be referring to this definition.
She will perform $$$1 \leq Q \leq 3,000$$$ changes. In each change, she will dig up one of the snack, and rebury it somewhere else, again at integer coordinates $$$X_{new}, Y_{new} \leq 100,000$$$. She wants to know that after each change, does the SPDL become lexicographically larger, smaller, or remain equal? See notes for a formal definition of lexicographical order.
In the first sample, suppose that she bought $$$N = 4$$$ Yubi's, buried at $$$P_0=(0,0)$$$, $$$P_1=(4,0)$$$, $$$P_2=(0,3)$$$, $$$P_3=(5,5)$$$, then the SPDL is $$$L_0 = \{9,16,25,26,29,50\}$$$, contributed by the distances of pair $$$\{(P_0,P_2),(P_0,P_1),(P_1,P_2),(P_1,P_3),(P_2,P_3),(P_0,P_3)\}$$$. The positions and their Euclidean distances (which is just the square root of our distance) are illustrated below.
Suppose that she then digs up $$$P_3$$$ and reburies it at $$$(1,2)$$$. The SPDL then becomes $$$L_1 = \{2,5,9,13,16,25\}$$$ instead. The smallest index where $$$L_0 \neq L_1$$$ is $$$0$$$ and the $$$0^{th}$$$ element in $$$L_1$$$ is smaller than in $$$L_0$$$, hence the SPDL became smaller.
She told her trusted friend Risuna "Have confidence!" and tasked them with this job. But Risuna has no confidence of doing it correctly and seeks your help. Can you help Risuna out?
The first line consists of two integers, $$$N$$$ and $$$Q$$$, denoting the number of Yubi's and the number of changes.
Then $$$N$$$ lines follow. The $$$i^{th}$$$ line of the $$$N$$$ lines ($$$0$$$-indexed) contains two integers, representing the initial coordinate of the $$$i^{th}$$$ Yubi.
Then $$$Q$$$ lines follow. Each line is represented by the three integers $$$W, X_{new}, Y_{new}$$$ representing the change $$$W^{th}$$$ Yubi (also $$$0$$$-indexed) being reburied to location $$$(X_{new}, Y_{new})$$$
After each change, output one line "larger", "smaller", or "equal" (without quotes) denoting if the SPDL became lexicographically larger, smaller or remain equal respectively.
Subtask 1 (23 points): $$$N,Q \leq 300$$$, $$$X,Y,X_{new},Y_{new} \leq 3,000$$$
Subtask 2 (43 points): $$$X,Y,X_{new},Y_{new} \leq 100$$$
Subtask 3 (21 points): $$$X,Y,X_{new},Y_{new} \leq 3,000$$$
Subtask 4 (13 points): No additional constraints
4 1 0 0 4 0 0 3 5 5 3 1 2
smaller
4 3 1 1 0 2 5 3 0 5 1 5 5 1 4 1 2 5 3
larger larger equal
Consider two lists $$$A$$$ and $$$B$$$ of the same length. Let $$$A_i$$$ denote the $$$i^{th}$$$ element of $$$A$$$, similarly for $$$B$$$. If both $$$A$$$ and $$$B$$$ are the same ($$$A_i = B_i$$$ for all $$$i$$$), then we say they are lexicographically equal.
If not, let $$$k$$$ be the smallest index such that $$$A_k \neq B_k$$$. Then we say $$$A$$$ is lexicographically smaller than $$$B$$$ is $$$A_k \lt B_k$$$, otherwise $$$A$$$ is lexicographically larger.
You have watched all of Gura's streams since her debut in Hololive EN. You want to learn what her favourite food is. In order to do so, you jot down her favourite food every time she shows its name on stream. However, she can't seem to make up her mind on one favourite food, so sometimes the food she says may differ. Furthermore, Gura is notorious for misspelling words, so even the spelling of the same food may differ!
You have collected a list of strings $$$S_1, S_2, \dots, S_N$$$ ($$$1 \leq N$$$), which are mentioned in Gura's streams. All of the strings have a fixed length of $$$K \geq 2$$$. The score of a string $$$S_i$$$ is defined as the number of strings $$$S_j$$$ ($$$i$$$ and $$$j$$$ can be the same) such that $$$S_i$$$ and $$$S_j$$$ differ by at most one letter. More formally, $$$S_i = \overline{a_1a_2a_3\dots a_K}$$$ and $$$S_j=\overline{b_1b_2b_3\dots b_K}$$$ differ by $$$x$$$ letters if there are exactly $$$x$$$ distinct $$$idx$$$'s such that $$$a_{idx}\neq b_{idx}$$$.
Output a string $$$S_i$$$ with maximum score. If there are multiple such strings, output the lexicographical smallest string. Additionally, you should output the number of strings $$$S_i$$$ that can attain the maximum score.
The first line consists of two integers, $$$N$$$ and $$$K$$$ $$$(N \times K \leq 2 \times 10^{5})$$$, denoting the number of strings that you have jotted down and the fixed length of each string respectively.
The next $$$N$$$ lines each contain a string $$$S_i$$$ with length $$$K$$$, composed of only lowercase English alphabet ('a'-'z').
The first line consists of one string, which has the maximum score.
The second line consists of the number of strings that can attain the maximum score.
Subtask $$$1$$$ ($$$19$$$ points): $$$N \leq 100$$$
Subtask $$$2$$$ ($$$47$$$ points): $$$K \leq 10$$$
Subtask $$$3$$$ ($$$34$$$ points): No additional constraints
5 5 takos tacos fishy aaaaa fisty
fishy 4
In the sample, "takos" and "tacos" differ by one letter, so is "fishy" and "fisty". The other pairs all differ by more than one letter. The score for the strings are all $$$2$$$ except for "aaaaa", which has a score of $$$1$$$. There are $$$4$$$ strings in total with maximum score of $$$2$$$, and "fishy" is the lexicographically smallest among them.
You are Amelia Watson's diehard fan and want her to earn the most money from SuperChat among all Hololive EN members at all times. As a fan of the time-travelling detective, you naturally learned some of her time-travelling powers as well. However, it turns out that you weren't the only one!
$$$Q$$$ events will occur. Event $$$i$$$ is of the form: "A fan just donated $$$X_i$$$ dollars via SuperChat to Hololive member $$$S_i$$$ at time $$$T_i$$$." After every event, find out the minimum amount you need to spend to ensure that Amelia earns the most money among all Hololive EN members $$$\textbf {at every point in time}$$$ (she is allowed to tie with some of them). You may travel to $$$\textbf {any}$$$ point in time to donate money via SuperChat.
Notes:
- The 5 members of Hololive EN are: Amelia, Calliope, Gura, Ina, and Kiara.
- If $$$T_i = T_j$$$ then events $$$Q_i$$$ and $$$Q_j$$$ would occur simultaneously.
- We recommend using fast input-output functions as the input size is large.
- This problem may require the use of 64-bit integer data types ("long long" in C++)
The first line contains a single integer $$$Q$$$ - the number of events ($$$1 \leq Q \leq 300,000$$$)
Then, $$$Q$$$ lines follow, each consisting of a single name $$$S_i$$$, and two integers $$$X_i$$$ and $$$T_i$$$. ($$$S_i \in$$$ {"Amelia", "Calliope", "Gura", "Ina", "Kiara"}, $$$1 \leq {X_i}, {T_i} \leq 1,000,000,000$$$)
Output $$$Q$$$ integers - the minimum $$$\textbf {total}$$$ amount of money you need to spend to ensure that Amelia earns the most at every point in time after each event.
Let $$$Q_{Amelia}$$$ be the number of queries where $$$S_i = $$$"Amelia"
Subtask 1 (13 points): $$$Q \leq 3000$$$
Subtask 2 (8 points): $$$Q_{Amelia} = 0$$$
Subtask 3 (14 points): $$$Q_{Amelia} \leq 5$$$
Subtask 4 (43 points): $$$S_i =$$$ "Amelia" or $$$S_i =$$$ "Kiara"
Subtask 5 (22 points): No additional constraints
3 Kiara 50 30 Gura 10 40 Amelia 40 25
50 50 10
10 Amelia 30 25 Gura 20 20 Ina 39 60 Ina 2 1 Kiara 31 23 Amelia 100 100 Calliope 35 300 Gura 204 96 Ina 100 3 Amelia 20 1000000000
0 20 20 20 31 31 31 194 194 194
For the first sample:
Someone time-travelled to $$$T = 30$$$ to give $$$50$$$ dollars to Kiara, so you could travel back to $$$T = 23$$$ and give $$$50$$$ dollars to Amelia to make sure Amelia doesn't earn less than Kiara when Kiara's Superchat arrives.
After that, someone else time-travelled to $$$T = 40$$$ to give $$$10$$$ dollars to Gura at $$$T = 40$$$. However, you have already given $$$50$$$ dollars to Amelia previously, so you do not need to give any more to Amelia as she already earned more than Gura.
Following that, a third person travelled back in time to $$$T = 25$$$ to give $$$40$$$ dollars to Amelia. Because of this, you could travel back in time to $$$T = 23$$$, stop yourself from giving $$$50$$$ dollars to Amelia, and instead only give $$$10$$$ dollars to Amelia to minimize the amount of money you spend.
hezlik has a tree with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$, and each vertex has a value $$$a_i$$$. All $$$a_i$$$'s are distinct.
There are two non-negative integers $$$c$$$ and $$$d$$$. For a simple path $$$P$$$, let $$$V$$$ be the set of all the vertices on the path $$$P$$$. We define the beauty of path P as: $$$$$$ c \cdot \mathop{\operatorname{mex}}\limits_{x\in V } \{ a_x \} + d \cdot \max\limits_{x\in V} \{ a_x \} $$$$$$ hezlik wants to know the maximum beauty among all simple paths. Can you help him?
Note: $$$\operatorname{mex} V$$$ is the smallest non-negative integer that does not belong to $$$V$$$, $$$\max V$$$ is the maximum integer that does belong to $$$V$$$.
A simple path is a sequence of distinct vertices $$$x_1, x_2, \dots , x_k$$$ where $$$k \ge 1$$$ such that there is an edge $$$(x_i, x_{i+1})$$$ for all integers $$$i$$$ where $$$1 \le i \le k-1$$$.
The first line consists of three space-separated integers $$$n,c,d$$$ ($$$2\le n\le 10^5$$$, $$$0\le c,d\le 10^9$$$).
The second line consists of $$$n$$$ space-separated integers $$$a_1,a_2,\cdots,a_{n}$$$ ($$$0\le a_i\le n-1$$$).
Each of the next $$$n-1$$$ lines contains two space-separated integers $$$u$$$ and $$$v$$$ ($$$1\le u,v\le n$$$), denoting there is an edge between $$$u$$$ and $$$v$$$.
Output a single integer, the maximum beauty among all simple paths.
5 2 3 0 1 2 3 4 1 2 1 3 2 4 2 5
18
20 1 1 10 18 13 8 19 15 0 14 11 17 12 5 4 9 16 2 1 6 7 3 17 9 6 17 20 17 4 17 18 9 15 17 2 18 13 2 3 20 12 15 10 18 5 3 11 20 7 13 16 12 1 12 8 15 19 11 14 7
21
Sample $$$1$$$: For the simple path $$$P=\{ 3,1,2,5 \}$$$, $$$\mathop{\operatorname{mex}}\limits_{x\in V } \{ a_x \}=\operatorname{mex}\{ 0,1,2,4 \}=3,\max\limits_{x\in V} \{ a_x \}=\max\{ 0,1,2,4 \}=4$$$, so the beauty of the simple path $$$P$$$ is $$$2\times 3+3\times 4=18$$$.
There are $$$n$$$ monsters in the Underworld. Monster $$$i$$$ has attributes $$$a_i$$$ and $$$b_i$$$. Calliope has $$$m$$$ one-time use scythes, where scythe $$$i$$$ has power $$$d_i$$$. Calliope can kill monster $$$i$$$ with scythe $$$j$$$ if $$$d_j \geq a_i$$$ OR $$$d_j \leq b_i$$$. Each scythe can only be used to kill one monster.
Find the maximum number of monsters that Calliope can kill.
The first line consists of two space-separated integers, $$$n$$$ and $$$m$$$ $$$(1 \leq n,m \leq 10^6)$$$.
The second line consists of $$$n$$$ space-separated integers, $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$.
The third line consists of $$$n$$$ space-separated integers, $$$b_1, b_2, \ldots, b_n$$$ $$$(1 \leq b_i \leq 10^9)$$$.
The fourth line consists of $$$m$$$ space-separated integers, $$$d_1, d_2, \ldots, d_m$$$ $$$(1 \leq d_i \leq 10^9)$$$.
Output a single integer, the maximum number of monsters that Calliope can kill.
Subtask 1 (8 points): $$$b_i=1,\,d_i \geq 2$$$ for all $$$i$$$
Subtask 2 (7 points): $$$1 \leq n,m \leq 11$$$
Subtask 3 (8 points): $$$1 \leq n,m \leq 100$$$
Subtask 4 (7 points): $$$1 \leq n,m \leq 500$$$
Subtask 5 (12 points): $$$1 \leq n,m \leq 3000$$$
Subtask 6 (43 points): $$$1 \leq n,m \leq 10^5$$$
Subtask 7 (15 points): No additional constraints
5 4 10 10 6 6 6 3 4 1 2 1 6 5 7 6
3
6 5 3 7 9 4 6 8 1 2 2 3 4 2 3 2 5 3 4
4
3 4 8 9 10 1 2 3 4 5 6 7
0
For convenience, define a-kill and b-kill as killing with $$$d_j\geq a_i$$$ and $$$d_j \leq b_i$$$ respectively.
Sample 1: The monster $$$(a,b)$$$-pairs are $$$(10,3),(10,3),(6,1),(6,2),(6,1)$$$. One way to kill $$$3$$$ monsters is to use scythes $$$1,3,4$$$ (with values $$$6,7,6$$$) to a-kill monsters $$$3,4,5$$$ respectively. Scythe $$$2$$$ cannot kill any monster, so the answer is $$$3$$$.
Sample 2: One way to achieve the answer: Scythes $$$1,3$$$ a-kill monsters $$$1,4$$$ respectively; scythes $$$2,4$$$ b-kill monsters $$$2,5$$$ respectively.
Sample 3: None of the scythes can kill any monster, so the answer is $$$0$$$.