antontrygubO_o UOI problems
2023_1A. An Array and Several More Arrays
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$k$$$ arrays of integers $$$a_1, a_2, \ldots, a_k$$$, where the array with index $$$i$$$ contains $$$l_i$$$ elements. Let $$$n = l_1 + l_2 + \ldots + l_k$$$.

You need to find $$$k$$$ integers $$$d_1, d_2, \ldots, d_k$$$ such that the numbers $$$(a_{i,j} + d_i)$$$ are pairwise distinct and satisfy $$$1 \leq a_{i,j} + d_i \leq n$$$.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^4$$$, $$$1 \le k \le 5$$$) – the total number of elements in the arrays and the number of arrays, respectively.

The next $$$k$$$ lines contain the arrays. The $$$i$$$-th line contains an integer $$$l_i$$$ ($$$1\le l_i\le n$$$) and $$$l_i$$$ integers $$$a_{i,1},a_{i,2},\ldots,a_{i,l_i}$$$ ($$$1 \le a_{i,j} \le n$$$) – the length and elements of the $$$i$$$-th array, respectively.

It is guaranteed that $$$n = l_1 + l_2 + \ldots + l_k$$$.

Output

If the required values of $$$d$$$ do not exist, output a single line "No".

Otherwise, output "Yes" on the first line.

On the second line, output $$$k$$$ integers $$$d_1,d_2,\ldots,d_k$$$ – the values that need to be added to the elements of the arrays to form a total of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$.

If there are multiple correct answers, any one of them may be output.

Scoring
  1. ($$$8$$$ points): $$$k=1$$$;
  2. ($$$9$$$ points): $$$a_{i,j}+1=a_{i,j+1}$$$ for $$$1 \le i \le k$$$, $$$1 \le j \lt l_i$$$;
  3. ($$$15$$$ points): $$$k \le 2$$$;
  4. ($$$21$$$ points): $$$k \le 3$$$;
  5. ($$$10$$$ points): $$$a_{i,j}+2=a_{i,j+1}$$$ for $$$1 \le i \le k$$$, $$$1 \le j \lt l_i$$$;
  6. ($$$10$$$ points): $$$(\max_{j \in [1;l_i]} a_{i,j}) - (\min_{j \in [1;l_i]} a_{i,j})=(n-k)$$$ for $$$1 \le i \le k$$$;
  7. ($$$10$$$ points): $$$n \le 30$$$;
  8. ($$$17$$$ points): without additional constraints.
Examples
Input
5 5
1 1
1 2
1 3
1 4
1 5
Output
Yes
0 0 0 0 0
Input
6 4
2 2 3
1 6
1 4
2 1 5
Output
Yes
1 -5 1 1
Input
7 2
4 1 4 5 6
3 1 2 6
Output
Yes
0 1
Input
4 2
2 2 3
2 2 4
Output
No
Note

In the first example, $$$d = [0,0,0,0,0]$$$ satisfies the condition, since after adding the corresponding values, the arrays $$$[1]$$$, $$$[2]$$$, $$$[3]$$$, $$$[4]$$$, $$$[5]$$$ are formed.

In the second example, $$$d = [1,-5,1,1]$$$ satisfies the condition, since after adding the corresponding values, the arrays $$$[3,4]$$$, $$$[1]$$$, $$$[5]$$$, $$$[2,6]$$$ are formed.

In the third example, $$$d = [0,1]$$$ satisfies the condition, since after adding the corresponding values, the arrays $$$[1,4,5,6]$$$ and $$$[2,3,7]$$$ are formed.

2023_1C. An Array and Range Additions
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array of integers $$$a$$$ of length $$$n$$$.

You can modify the array using the addition operation. To apply the addition operation, you need to perform three sequential actions:

  1. Choose any integer $$$x$$$.
  2. Choose any subarray $$$[l;r]$$$ of the array.
  3. Add $$$x$$$ to each element of the chosen subarray (perform the assignment operation $$$a_i \leftarrow (a_i+x)$$$ for $$$l \le i\le r$$$).

Find the minimum number of addition operations required to make all elements of the array $$$a$$$ pairwise distinct.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array.

Output

Output a single integer — the minimum number of addition operations required to make all elements of the array $$$a$$$ pairwise distinct.

Scoring
  1. ($$$9$$$ points): all elements of the array $$$a$$$ are equal to $$$1$$$.
  2. ($$$15$$$ points): $$$1 \le a_i \le 2$$$ for $$$1 \le i \le n$$$; $$$a_i \le a_{i+1}$$$ for $$$1 \le i \lt n$$$.
  3. ($$$14$$$ points): $$$n \le 8$$$.
  4. ($$$17$$$ points): $$$a_1 = a_n$$$.
  5. ($$$12$$$ points): $$$n \le 2000$$$.
  6. ($$$12$$$ points): $$$1 \le a_i \le 100$$$ for $$$1\le i\le n$$$.
  7. ($$$21$$$ points): no additional constraints.
Examples
Input
3
1 2 3
Output
0
Input
5
2 3 2 3 2
Output
2
Input
9
2 3 1 1 3 2 1 3 3
Output
2
Note

In the first example, all elements of the array $$$a$$$ are pairwise distinct.

In the second example, after applying two addition operations with parameters $$$x=-3$$$, $$$l=1$$$, $$$r=2$$$ and $$$x=-1$$$, $$$l=1$$$, $$$r=3$$$, the array $$$a$$$ becomes equal to $$$[-2,-1,1,3,2]$$$.

In the third example, after applying two addition operations with parameters $$$x=-3$$$, $$$l=4$$$, $$$r=8$$$ and $$$x=-10$$$, $$$l=7$$$, $$$r=9$$$, the array $$$a$$$ becomes equal to $$$[2,3,1,-2,0,-1,-12,-10,-7]$$$.

2023_2A. An Array and Medians of Subarrays
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Let's call the median of an array of length $$$(2 \cdot k + 1)$$$ the number that appears in position $$$(k + 1)$$$ after sorting its elements in non-decreasing order. For example, the medians of the arrays $$$[1]$$$, $$$[4,2,5]$$$, and $$$[6,5,1,2,3]$$$ are $$$1$$$, $$$4$$$, and $$$3$$$, respectively.

You are given an array of integers $$$a$$$ of even length $$$n$$$.

Determine whether it is possible to split $$$a$$$ into several subarrays of odd length such that all the medians of these subarrays are pairwise equal.

Formally, you need to determine whether there exists a sequence of integers $$$i_1, i_2, \ldots, i_k$$$ such that the following conditions are satisfied:

  • $$$1 = i_1 \lt i_2 \lt \ldots \lt i_k = (n + 1)$$$;
  • $$$(i_2 - i_1) \mod 2 = (i_3 - i_2) \mod 2 = \ldots = (i_k - i_{k - 1}) \mod 2 = 1$$$;
  • $$$f(a[i_1..(i_2-1)]) = f(a[i_2..(i_3-1)]) = \ldots = f(a[i_{k - 1}..(i_k - 1)])$$$, where $$$a[l..r]$$$ denotes the subarray consisting of elements $$$a_l, a_{l + 1}, \ldots, a_r$$$, and $$$f(a)$$$ denotes the median of the array $$$a$$$.
Input

The first line contains a single even integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of the array.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le 10^9)$$$ — the elements of the array.

It is guaranteed that $$$n$$$ is even.

Output

Output "Yes" if it is possible to divide $$$a$$$ into several subarrays of odd length in such a way that all medians of these subarrays are pairwise equal, and "No" otherwise.

Scoring
  1. ($$$3$$$ points): $$$n=2$$$;
  2. ($$$14$$$ points): $$$1 \le a_i \le 2$$$ for $$$1\le i\le n$$$;
  3. ($$$12$$$ points): $$$a_i \le a_{i+1}$$$ for $$$1\le i \lt n$$$;
  4. ($$$16$$$ points): $$$1 \le a_i \le 3$$$ for $$$1 \le i \le n$$$; each value occurs in $$$a$$$ no more than $$$n \over 2$$$ times;
  5. ($$$17$$$ points): $$$n \le 100$$$;
  6. ($$$18$$$ points): $$$n \le 2000$$$;
  7. ($$$20$$$ points): no additional restrictions.
Examples
Input
4
1 1 1 1
Output
Yes
Input
6
1 2 3 3 2 1
Output
Yes
Input
6
1 2 1 3 2 3
Output
No
Note

In the first example, the array $$$[1,1,1,1]$$$ can be divided into the arrays $$$[1]$$$ and $$$[1,1,1]$$$ with medians equal to $$$1$$$.

In the second example, the array $$$[1,2,3,3,2,1]$$$ can be divided into the arrays $$$[1,2,3]$$$ and $$$[3,2,1]$$$ with medians equal to $$$2$$$.

In the third example, the array $$$[1,2,1,3,2,3]$$$ cannot be divided into several arrays of odd length with the same median values.

2023_2B. An Array of Characters and Almost Palindromes
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

A string is considered a palindrome if it reads the same from both sides. Formally, a string $$$s$$$ of length $$$n$$$ is considered a palindrome if $$$s_i = s_{n-i+1}$$$ for $$$1 \le i \le n$$$. For example, the strings "gg", "ara", "abacaba", and "rotator" are palindromes, while the strings "array", "palindrome", and "uoi" are not.

We call a string a nearly palindrome if its characters can be rearranged to form a palindrome. For example, the strings "n", "ara", "arr", and "array" are nearly palindromes, while the strings "palindrome", "uoi", and "random" are not.

A substring of a string is a string that can be obtained by deleting some (possibly zero) elements from its beginning and end.

Let $$$f(s)$$$ be the maximum length among the lengths of substrings of $$$s$$$ that are not nearly palindromes, or $$$0$$$ if there are no such substrings.

You are given a string $$$s$$$ of length $$$n$$$ consisting of lowercase Latin letters. You are also given $$$q$$$ queries of the form $$$l_i$$$, $$$r_i$$$. For each query, find the value of $$$f(s[l_i..r_i])$$$, where $$$s[l_i..r_i]$$$ denotes the substring consisting of characters $$$s_{l_i}, s_{l_{i} + 1}, \ldots, s_{r_i}$$$.

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — the length of the string.

The second line contains a string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters.

The third line contains one integer $$$q$$$ ($$$1\le q \le 2\cdot 10^5$$$) — the number of queries.

The fourth line contains two integers $$$l_1, r_1$$$ ($$$1 \leq l_1 \leq r_1 \leq n$$$) — the parameters of the first query.

You will receive the parameters of the next queries from the jury program (see section "Interaction Protocol").

Output

For each $$$i$$$-th query, output one integer — the value of $$$f(s[l_i..r_i])$$$, in a separate line.

Interaction

The jury program will output two integers $$$l_i$$$, $$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$) on separate lines for each query, starting from the second one.

The jury program will not output the parameters for the next query until it reads the response of your program to the previous query.

Make sure to call the flush method after outputting each line. You can use:

  • fflush(stdout), cout <{}< endl, or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • sys.stdout.flush() in Python;
  • consult the documentation for other programming languages.
Scoring
  1. ($$$6$$$ points): $$$q=1$$$, $$$l_1=1$$$, $$$r_1=n$$$, $$$n$$$ is even, $$$s$$$ has the form "aabbaabbaa...";
  2. ($$$9$$$ points): $$$q=1$$$, $$$l_1=1$$$, $$$r_1=n$$$, $$$n \le 200$$$;
  3. ($$$5$$$ points): $$$q=1$$$, $$$l_1=1$$$, $$$r_1=n$$$, $$$n \le 5000$$$;
  4. ($$$8$$$ points): $$$q=1$$$, $$$l_1=1$$$, $$$r_1=n$$$;
  5. ($$$10$$$ points): $$$s$$$ contains only letters a and b;
  6. ($$$8$$$ points): $$$s_{l_i} \neq s_{r_i}$$$ for $$$1 \le i \le q$$$;
  7. ($$$7$$$ points): $$$s_i \neq s_{i+1}$$$ for $$$1 \le i \lt n$$$;
  8. ($$$10$$$ points): $$$s$$$ contains only letters a, b, c, d, e, and f;
  9. ($$$18$$$ points): $$$(r_i-l_i+1)$$$ is odd for $$$1\le i\le q$$$;
  10. ($$$19$$$ points): without additional constraints.
Example
Input
8
aabaaaba
3
3 7
1 8
4 4
Output
4
6
0
Note

In the first example, you need to find the answers to three queries:

  1. $$$s[3..7] =\;$$$"baaab", which has a substring "aaab" of length 4, which is not an almost palindrome;
  2. $$$s[1..8] =\;$$$"aabaaaba", which has a substring "aabaaa" of length 6, which is not an almost palindrome;
  3. $$$s[4..4] =\;$$$"a", all substrings of which are almost palindromes.

2024_1C. Queries for Subarray Beauty
time limit per test
2.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Let's call the weight of an array of integers $$$b$$$ of length $$$m$$$ the absolute value of the sum of its elements, i.e., $$$|b_1+b_2+...+b_m|$$$.

We define the beauty of a partition of array $$$c$$$ into several subarrays as the minimum weight among the weights of the subarrays. Formally, the beauty of a partition of array $$$c$$$ into $$$k$$$ subarrays $$$[c_1,\ldots,c_{p_1}],[c_{p_1+1},\ldots,c_{p_2}],\ldots,[c_{p_{k-1}+1},\ldots,c_{p_k}]$$$, where $$$1 \leq p_1 \lt p_2 \lt \ldots \lt p_{k-1} \lt p_k = n$$$, is the value $$$\min(|c_1+\ldots+c_{p_1}|,|c_{p_1+1}+\ldots+c_{p_2}|,\ldots,|c_{p_{k-1}+1}+\ldots+c_{p_k}|)$$$. For example, the partition of the array $$$[3,-6,4,5,-8]$$$ into subarrays $$$[3,-6],[4],[5,-8]$$$ has a beauty of $$$\min(|3+(-6)|,|4|,|5+(-8)|)=\min(3,4,3)=3$$$.

We define the beauty of an array $$$c$$$ as the maximum beauty among all possible partitions into subarrays.

An array of integers $$$a$$$ of length $$$n$$$ is given.

You need to perform $$$q$$$ queries. The queries can be of two types:

  1. find the beauty of the subarray consisting of elements $$$[a_{l},a_{l+1},\ldots,a_r]$$$, where ($$$l$$$, $$$r$$$) are the query parameters;
  2. replace the element $$$a_x$$$ with $$$v$$$, where ($$$x$$$, $$$v$$$) are the query parameters.
Input

The first line contains two integers $$$n$$$, $$$q$$$ ($$$1\le n, q\le 10^6$$$) — the length of array $$$a$$$ and the number of queries, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9\le a_i\le 10^9)$$$ — the elements of array $$$a$$$.

The next $$$q$$$ lines contain three integers each. The first of the numbers, $$$type_i$$$ ($$$1 \le type_i \le 2$$$), denotes the type of the query. Queries of the first type are given in the format "1 l r" ($$$1\le l\le r\le n$$$), and queries of the second type are given in the format "2 x v" ($$$1\le x\le n,$$$ $$$-10^9\le v\le 10^9$$$).

Output

For each query of the first type, output a single integer — the beauty of the corresponding subarray.

Scoring
  1. ($$$4$$$ points): $$$type_i = 1$$$ for $$$1\le i\le q$$$; $$$a_i \gt 0$$$ for $$$1\le i\le n$$$;
  2. ($$$14$$$ points): $$$type_i = 1$$$ for $$$1\le i\le q$$$; $$$n,q \le 1000$$$;
  3. ($$$10$$$ points): $$$type_i = 1$$$ for $$$1\le i\le q$$$; $$$n,q \le 2 \cdot 10^5$$$, for each query there exists an optimal division into no more than $$$2$$$ subarrays;
  4. ($$$10$$$ points): $$$type_i = 1$$$ for $$$1\le i\le q$$$; $$$q \le n \le 2 \cdot 10^5$$$, $$$l_i = 1$$$, $$$r_i = i$$$ for $$$1\le i\le q$$$;
  5. ($$$11$$$ points): $$$type_i = 1$$$ for $$$1\le i\le q$$$; $$$n,q \le 2 \cdot 10^5$$$, $$$-5 \le \sum\limits_{j=1}^{i} a_j \le 5$$$ for $$$1\le i\le n$$$;
  6. ($$$18$$$ points): $$$type_i = 1$$$ for $$$1\le i\le q$$$; $$$n,q \le 2 \cdot 10^5$$$;
  7. ($$$9$$$ points): $$$type_i = 1$$$ for $$$1\le i\le q$$$;
  8. ($$$16$$$ points): $$$n,q \le 2 \cdot 10^5$$$;
  9. ($$$8$$$ points): without additional constraints.
Examples
Input
6 4
1 -3 4 2 -5 6
1 1 6
1 2 3
1 2 5
1 1 1
Output
5
3
3
1
Input
5 6
1 -2 3 -4 5
1 1 4
1 2 3
2 3 -6
1 2 4
2 4 2
1 1 5
Output
2
2
12
7
Note

In the first example, for the third query, the maximum beauty of the partition of the array $$$[-3,4,2,-5]$$$ is achieved when partitioned into subarrays $$$[-3],[4,2],[-5]$$$.

In the second example, for the first query, the maximum beauty of the partition of the array $$$[1,-2,3,-4]$$$ is achieved when partitioned into subarrays $$$[1,-2,3],[-4]$$$.

2024_2A. Colorful Table
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a table $$$a$$$ of size $$$n \times m$$$, consisting of symbols "R", "G", "B".

Also, given are integers $$$c$$$ ($$$2 \leq c \leq 3$$$) and $$$q$$$, where $$$c$$$ is the number of different symbols that can appear in the table. If $$$c$$$ equals $$$2$$$, only the symbols "R" and "G" are available; if $$$c$$$ equals $$$3$$$, the symbols "R", "G", "B" are available.

You need to change the values of at most $$$q$$$ elements of the table so that there are no pairs of neighboring cells with the same value. Note that if $$$c=2$$$, using the symbol "B" when changing the values of the table cells is prohibited.

It is guaranteed that under the given constraints, there is a way to change the values of at most $$$q$$$ elements of the table so that there are no pairs of neighboring cells with the same value.

Note that there are no additional constraints in the problem.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 100$$$) — the number of rows and columns of the table $$$a$$$ respectively.

The second line contains two integers $$$c$$$ ($$$2 \leq c \leq 3$$$) and $$$q$$$, representing the number of available symbols and the number of allowed changes in the table, respectively.

The next $$$n$$$ lines contain $$$m$$$ symbols each — the elements of the table $$$a$$$. If $$$c=2$$$, then $$$a_{ij} \in $$$ {"R", "G"}. If $$$c=3$$$, then $$$a_{ij} \in $$$ {"R", "G", "B"}.

Output

Output $$$n$$$ lines of $$$m$$$ symbols each, describing the table after the changes.

If there are multiple correct answers, any of them is allowed.

Scoring
  1. ($$$7$$$ points): $$$n = 1,\ c = 3,\ q = \lfloor \frac{n \cdot m}{2} \rfloor $$$;
  2. ($$$7$$$ points): $$$n = 1,\ c = 2,\ q = \lfloor \frac{n \cdot m}{2} \rfloor$$$;
  3. ($$$3$$$ points): $$$c = 3,\ q = n \cdot m$$$;
  4. ($$$7$$$ points): all rows of table $$$a$$$ are the same, $$$a[1][j] \neq a[1][j+1]$$$ (for $$$1 \leq j \lt m$$$), $$$c = 3$$$, $$$q = \lfloor \frac{n \cdot m}{2} \rfloor$$$;
  5. ($$$7$$$ points): all rows of table $$$a$$$ are the same, $$$c = 3$$$, $$$q = \lfloor \frac{n \cdot m}{2} \rfloor$$$;
  6. ($$$13$$$ points): $$$c = 3,\ q = \lfloor \frac{2 \cdot n \cdot m}{3} \rfloor $$$;
  7. ($$$19$$$ points): $$$c = 3,\ n \leq 5,\ m \leq 100,\ q = \lfloor \frac{n \cdot m}{2} \rfloor$$$;
  8. ($$$17$$$ points): $$$c = 2,\ q = \lfloor \frac{n \cdot m}{2} \rfloor$$$;
  9. ($$$20$$$ points): $$$c = 3,\ q = \lfloor \frac{n \cdot m}{2} \rfloor$$$.
Examples
Input
3 3
3 4
RRR
RRR
RRR
Output
RGR
GRG
RGR
Input
3 2
2 3
RG
GG
GR
Output
RG
GR
RG

2024_2C. Heroes and Monsters
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

There are $$$n$$$ heroes and $$$n$$$ monsters. The heroes and monsters are numbered with integers from $$$1$$$ to $$$n$$$. The strength of the $$$i$$$-th hero is equal to $$$a_i$$$, and the strength of the $$$i$$$-th monster is equal to $$$b_i$$$. It is guaranteed that all values $$$a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n$$$ are pairwise distinct.

There will be a total of $$$n$$$ battles. In each battle, exactly one hero and exactly one monster will participate, with each hero and each monster participating in exactly one battle. Let the battle involve the hero with number $$$i$$$ and the monster with number $$$j$$$. If $$$a_i \gt b_j$$$, then the hero with number $$$i$$$ will be happy, otherwise, he will be sad.

Let $$$ans_k$$$ be the number of different sets of heroes $$$S$$$ of size $$$k$$$, such that there is a distribution of battles where all heroes in $$$S$$$ will be happy and all other heroes will be sad.

Given $$$q$$$ queries of the form $$$l$$$, $$$r$$$. For each query, find $$$(\sum\limits_{i=l}^{r} ans_i) \mod 998244353$$$.

Input

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^3$$$) — the number of battles that will take place.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 2 \cdot n$$$) — the strengths of the heroes.

The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ $$$(1 \leq b_i \leq 2 \cdot n)$$$ — the strengths of the monsters.

It is guaranteed that all values $$$a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n$$$ are pairwise distinct.

The fourth line contains a single integer $$$q$$$ $$$(1 \leq q \leq n+1)$$$ — the number of queries.

The next $$$q$$$ lines contain two integers each, $$$l$$$ and $$$r$$$ $$$(0 \leq l \leq r \leq n)$$$ — the parameters of the corresponding query.

It is guaranteed that all values $$$a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n$$$ are pairwise distinct.

Output

For each query, output a single integer — the required value $$$(\sum\limits_{i=l}^{r} ans_i) \mod 998244353$$$.

Scoring
  1. ($$$3$$$ points): $$$a_i \lt b_j$$$ for $$$1 \leq i,j \leq n$$$;
  2. ($$$9$$$ points): $$$q = 1$$$, $$$l = 1$$$, $$$r = 1$$$;
  3. ($$$6$$$ points): $$$a_i = 2 \cdot i - 1$$$, $$$b_i = 2 \cdot i$$$ for $$$1 \leq i \leq n$$$;
  4. ($$$16$$$ points): $$$n \leq 500$$$, $$$q = 1$$$, $$$l = 0$$$, $$$r = n$$$;
  5. ($$$14$$$ points): $$$q = 1$$$, $$$l = 0$$$, $$$r = n$$$;
  6. ($$$15$$$ points): $$$q = 1$$$, $$$l=r$$$;
  7. ($$$17$$$ points): $$$n \leq 500$$$;
  8. ($$$20$$$ points): without additional restrictions.
Example
Input
3
3 4 6
1 2 5
3
1 2
2 3
3 3
Output
2
3
1
Note

The image below shows the heroes and monsters of the first example. The heroes are at the top, and the monsters are at the bottom. The number inside the square represents the strength of the corresponding hero or monster.

In the example, there are three possible sets of happy heroes: $$$\{1,2,3\}$$$, $$$\{2,3\}$$$, and $$$\{1,3\}$$$. Below are three possible distributions of battles in which the corresponding sets of heroes will be happy. Note that there may be multiple distributions of battles where the same set of heroes will be happy.

2025_1A. Boys and Girls
time limit per test
2.75 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ types of boys and $$$2 \cdot n$$$ girls. The types of boys are numbered with integers from $$$1$$$ to $$$n$$$, while the girls are numbered with integers from $$$1$$$ to $$$2 \cdot n$$$.

There are $$$c_i$$$ boys of the $$$i$$$-th type, and each of them likes girls numbered $$$a_i$$$ and $$$b_i$$$.

Find the size of the largest set of boys such that for every pair of boys in this set, there is at least one girl that both of them like.

In this problem, each test contains several sets of input data. You need to solve the problem independently for each such set.

Input

The first line contains one integer $$$T$$$ $$$(1 \le T \le 500)$$$ — the number of sets of input data. The description of the input data sets follows.

In the first line of each input data set, there is one integer $$$n$$$ $$$(1 \le n \le 7 \cdot 10^5)$$$.

In the next $$$n$$$ lines, there are three integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ $$$(1 \le a_i \lt b_i \le 2 \cdot n, 1 \le c_i \le 10^9)$$$ — the parameters for the corresponding type of boys.

It is guaranteed that $$$a_i \ne a_j$$$ or $$$b_i \ne b_j$$$ for any $$$1 \le i \lt j \le n$$$.

It is guaranteed that the sum of $$$n$$$ across all input data sets of a single test does not exceed $$$7 \cdot 10^5$$$.

Output

For each set of input data, output one integer on a separate line — the size of the largest set of boys such that for every pair of boys in this set, there is at least one girl that both of them like.

Scoring

Let $$$S$$$ be the sum of $$$n$$$ over all test case input sets of one test, and $$$K$$$ be the sum of all $$$c_i$$$ over all test case input sets of one test.

  1. ($$$5$$$ points): $$$n \le 5$$$;
  2. ($$$11$$$ points): $$$S \le 100$$$;
  3. ($$$7$$$ points): each girl is liked by boys of no more than two types;
  4. ($$$10$$$ points): $$$S \le 3000$$$;
  5. ($$$23$$$ points): $$$S \le 3 \cdot 10^5$$$;
  6. ($$$19$$$ points): $$$K \le 10^7$$$;
  7. ($$$25$$$ points): with no additional constraints.
Example
Input
3
2
1 2 3
3 4 5
5
1 2 1
1 3 4
4 5 2
3 4 2
1 4 3
4
1 2 3
2 3 4
3 5 4
1 3 2
Output
5
9
10

2025_1B. Partitioning into Three
time limit per test
0.3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ non-negative integers $$$a_1, a_2, \ldots, a_n$$$ arranged in a circle. The neighboring numbers in the circular order are $$$a_1$$$ and $$$a_2$$$, $$$a_2$$$ and $$$a_3$$$, $$$\ldots$$$, $$$a_{n-1}$$$ and $$$a_n$$$, $$$a_n$$$ and $$$a_1$$$.

Partition these numbers into three non-empty groups such that each number belongs to exactly one group, the numbers in each group are consecutively arranged in a circle, and the difference between the maximum and minimum sums of the numbers in the groups is minimized.

Input

The first line contains one integer $$$n$$$ $$$(3 \le n \le 10^6)$$$ — the number of arranged numbers.

The second line contains $$$n$$$ non-negative integers $$$a_1, a_2, \ldots, a_n$$$ $$$(0 \le a_i \le 10^9)$$$ — the numbers arranged in a circle.

Output

In the first line, output one integer — the difference between the maximum and minimum sums of the numbers in the groups in the optimal partition.

In the second line, output three integers $$$x$$$, $$$y$$$, $$$z$$$ $$$(1 \le x \lt y \lt z \le n)$$$ — such indices that the optimal partition of the numbers into three groups is of the form $$$[a_{x}, a_{x+1}, \ldots, a_{y-1}]$$$, $$$[a_{y}, a_{y+1}, \ldots, a_{z-1}]$$$, $$$[a_{z}, a_{z+1}, \ldots, a_{n-1}, a_{n}, a_{1}, a_{2}, \ldots, a_{x-1}]$$$.

If there are multiple correct answers, any of them is allowed to be output.

Scoring
  1. ($$$2$$$ points): $$$n = 3$$$;
  2. ($$$4$$$ points): $$$a_i \le 1$$$ for $$$1 \le i \le n$$$;
  3. ($$$13$$$ points): there exists a partition where the sought difference is equal to $$$0$$$;
  4. ($$$8$$$ points): $$$n \le 100$$$;
  5. ($$$9$$$ points): $$$n \le 2000$$$;
  6. ($$$13$$$ points): $$$n \le 5000$$$;
  7. ($$$28$$$ points): $$$n \le 10^5$$$;
  8. ($$$23$$$ points): with no additional restrictions.
Examples
Input
4
1 2 3 4
Output
1
1 3 4
Input
7
1 6 1 0 5 3 2
Output
0
2 3 6
Input
8
3 1 4 1 5 9 2 6
Output
1
3 6 8
Note

In the third example, the optimal partition looks as follows:

In this case, the sums in the groups are $$$10$$$, $$$11$$$, and $$$10$$$.

2025_1C. Convex Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array of integers $$$a$$$ of length $$$n$$$.

Determine whether there exists a permutation of its elements $$$b$$$ such that for every $$$2\leq i \leq n-1$$$, the condition $$$b_{i-1} + b_{i+1} \ge 2\cdot b_i$$$ holds.

In this problem, each test contains several sets of input data. You need to solve the problem independently for each such set.

Input

The first line contains a single integer $$$T$$$ $$$(1\le T\le 10^5)$$$ — the number of sets of input data. The description of the input data sets follows.

In the first line of each input data set, there is a single integer $$$n$$$ $$$(3\le n\le 3\cdot 10^5)$$$ — the length of the array $$$a$$$.

In the second line of each input data set, there are $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(0\le a_i\le 10^9)$$$ — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ across all input data sets of a single test does not exceed $$$3\cdot 10^5$$$.

Output

For each set of input data, output on a separate line "YES", if the desired permutation exists, and "NO" otherwise.

Scoring

Let $$$S$$$ be the sum $$$n$$$ over all input data sets of one test.

  1. ($$$3$$$ points): $$$n = 4$$$;
  2. ($$$4$$$ points): $$$T = 1$$$, $$$n \le 7$$$;
  3. ($$$7$$$ points): $$$T = 1$$$, $$$n \le 15$$$;
  4. ($$$5$$$ points): if some desired permutation exists, then there exists such a desired permutation for which $$$b_1 \ge b_2$$$ and $$$b_2 \le b_3$$$;
  5. ($$$17$$$ points): $$$S \le 50$$$;
  6. ($$$10$$$ points): $$$S \le 400$$$;
  7. ($$$13$$$ points): $$$S \le 2000$$$;
  8. ($$$9$$$ points): $$$S \le 8000$$$;
  9. ($$$18$$$ points): $$$a_i \le 10^6$$$ for $$$1 \le i \le n$$$;
  10. ($$$14$$$ points): without additional restrictions.
Example
Input
10
4
0 3 4 6
4
5 4 1 4
8
1 4 4 8 6 10 10 4
7
2 1 5 1 9 4 6
6
7 1 6 10 2 3
7
6 6 10 2 5 3 8
4
9 9 1 5
4
8 4 3 4
7
1 2 1 6 4 2 9
7
3 9 7 5 9 10 10
Output
YES
NO
NO
YES
YES
NO
YES
YES
YES
NO
Note

In the first set of input data from the first example, the permutations of the array $$$[0, 3, 4, 6]$$$ that satisfy the described condition are $$$[4, 0, 3, 6]$$$ and $$$[6, 3, 0, 4]$$$.

2025_1D. Simple Subsequence
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

We call an array of integers $$$d_1, d_2, \ldots, d_m$$$ good if its length is equal to $$$0$$$, or for any $$$1\le i\le m$$$, both values $$$\sum\limits_{j=1}^{i} d_j$$$ and $$$\sum\limits_{j=i}^{m} d_j$$$ are non-negative. Here, $$$\sum\limits_{j=l}^{r} d_j$$$ denotes $$$d_l+d_{l+1}+\ldots+d_{r}$$$.

We define the beauty of the array as the length of its longest good subsequence$$$^1$$$.

You are given an array $$$a$$$ of length $$$n$$$, which consists of numbers $$$-1$$$ and $$$1$$$.

You need to perform $$$q$$$ queries. The queries are of two types:

  1. replace the element $$$a_p$$$ with $$$-a_p$$$, where $$$p$$$ — the parameter of the query;
  2. find the beauty of the array consisting of elements $$$[a_{l},a_{l+1},\ldots,a_r]$$$, where $$$(l, r)$$$ — the parameters of the query.
Input

In the first line, two integers $$$n$$$, $$$q$$$ are given $$$(1\le n, q\le 5 \cdot 10^5)$$$ — the length of the array $$$a$$$ and the number of queries, respectively.

In the second line, $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(a_i \in \{-1, 1\})$$$ are given — the elements of the array $$$a$$$.

In the next $$$q$$$ lines, the description of the queries is given. The first of the numbers $$$type_i$$$ $$$(1 \le type_i \le 2)$$$ denotes the type of the query. Queries of the first type are given in the format "1 p" $$$(1 \le p \le n)$$$, and queries of the second type are given in the format "2 l r" $$$(1 \le l \le r \le n)$$$.

Output

For each query of the second type, output one integer in a separate line — the beauty of the corresponding array.

Scoring
  1. ($$$2$$$ points): $$$a_i = (-1)^{i+1}$$$ for $$$1 \le i \le n$$$, and there are no type one queries;
  2. ($$$7$$$ points): $$$n \le 16$$$, and there are no type one queries;
  3. ($$$21$$$ points): $$$n, q \le 100$$$;
  4. ($$$20$$$ points): $$$n, q \le 3000$$$;
  5. ($$$27$$$ points): $$$n, q \leq 2 \cdot 10^5$$$, and there are no type one queries;
  6. ($$$14$$$ points): $$$n, q \leq 2 \cdot 10^5$$$;
  7. ($$$9$$$ points): no additional restrictions.
Examples
Input
5 4
1 1 1 -1 1
2 1 5
1 3
2 1 4
2 2 5
Output
5
2
3
Input
4 4
1 1 1 -1
2 1 2
2 2 4
2 3 3
2 3 4
Output
2
2
1
1
Note

$$$^1$$$ An array $$$c$$$ is called a subsequence of an array $$$b$$$ if it is possible to remove a certain number of elements from the array $$$b$$$ (possibly zero) so that the array $$$c$$$ is formed. The empty array is a subsequence of any array.

2025_2A. Manhattan Pairing
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For a pair of points on the Cartesian plane $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$, we define the Manhattan distance between them as $$$|x_1-x_2|+|y_1-y_2|$$$. For example, for the pair of points $$$(4, 1)$$$ and $$$(2, 7)$$$, the Manhattan distance between them is $$$|4-2|+|1-7| = 2+6 = 8$$$.

You are given $$$2 \cdot n$$$ points on the Cartesian plane, whose coordinates are integers. All $$$y$$$-coordinates of the given points are either $$$0$$$ or $$$1$$$.

Split the given points into $$$n$$$ pairs such that each of these points belongs to exactly one pair, and the maximum Manhattan distance between the points of one pair is minimized.

Input

The first line contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$.

In the following $$$2 \cdot n$$$ lines, each line contains two integers $$$x_i$$$ and $$$y_i$$$ $$$(0 \le x_i \le 10^9, 0 \le y_i \le 1)$$$ — the coordinates of the corresponding point.

Output

Output a single integer — the maximum Manhattan distance between the points of one pair in the optimal partition.

Scoring
  1. ($$$2$$$ points): $$$n = 1$$$;
  2. ($$$3$$$ points): $$$x_i = 0$$$ for $$$1 \le i \le 2\cdot n$$$;
  3. ($$$4$$$ points): $$$n \le 4$$$;
  4. ($$$11$$$ points): $$$n \le 10$$$;
  5. ($$$14$$$ points): $$$y_i = 0$$$ for $$$1 \le i \le 2\cdot n$$$;
  6. ($$$10$$$ points): $$$x_i \neq x_j$$$ for $$$1 \le i \lt j \le 2\cdot n$$$;
  7. ($$$29$$$ points): $$$n \le 1000$$$;
  8. ($$$27$$$ points): no additional restrictions.
Examples
Input
1
3 1
1 0
Output
3
Input
3
18 0
3 0
1 0
10 0
8 0
14 0
Output
4
Input
4
3 0
0 1
5 0
2 1
6 0
3 0
5 1
2 1
Output
2
Note

In the second example, the pairing $$$[(18, 0), (14, 0)]$$$, $$$[(3, 0), (1, 0)]$$$, and $$$[(8, 0), (10, 0)]$$$ is the only optimal partition. The Manhattan distances between the points of one pair in this partition are $$$4$$$, $$$2$$$, and $$$2$$$, respectively.

In the third example, the pairing $$$[(0, 1), (2, 1)]$$$, $$$[(2, 1), (3, 0)]$$$, $$$[(3, 0), (5, 0)]$$$, and $$$[(5, 1), (6, 0)]$$$ is an optimal partition. All Manhattan distances between the points of one pair in this partition are equal to $$$2$$$.

Illustration for the third example

2025_2C. Reversal ABC
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a string $$$s$$$ consisting of characters $$$\texttt{A}$$$, $$$\texttt{B}$$$, and $$$\texttt{C}$$$.

In one operation, you are allowed to choose two adjacent elements of the string $$$s_is_{i+1}$$$ that are in the following order: $$$\texttt{AB}$$$, $$$\texttt{BC}$$$, or $$$\texttt{CA}$$$, and swap them.

Find the maximum number of consecutive operations that can be performed on the string $$$s$$$.

In this problem, each test contains several sets of input data. You need to solve the problem independently for each such set.

Input

The first line contains one integer $$$T$$$ $$$(1\le T\le 10^5)$$$ — the number of sets of input data. The description of the input data sets follows.

In the first line of each input data set, there is one integer $$$n$$$ $$$(1 \le n \le 10^6)$$$ — the length of the string $$$s$$$.

In the second line of each input data set, there is a string $$$s$$$ of length $$$n$$$, consisting of characters $$$\texttt{A}$$$, $$$\texttt{B}$$$, and $$$\texttt{C}$$$.

It is guaranteed that the sum of $$$n$$$ across all input data sets of a single test does not exceed $$$10^6$$$.

Output

For each set of input data, output on a separate line one integer — the maximum number of consecutive operations that can be performed on the string $$$s$$$.

Scoring

Let $$$K$$$ be the sum of $$$n$$$ over all input data sets of one test.

  1. ($$$2$$$ points): the answer is equal to $$$0$$$ or $$$1$$$;
  2. ($$$3$$$ points): $$$n \le 3$$$;
  3. ($$$5$$$ points): $$$s_i \ne \texttt{C}$$$ for $$$1 \le i \le n$$$;
  4. ($$$5$$$ points): $$$s$$$ has the form $$$\texttt{AA}\ldots \texttt{AABB}\ldots \texttt{BBCC}\ldots \texttt{CC}$$$ (that is, $$$x \cdot \texttt{A} + y \cdot \texttt{B} + z \cdot \texttt{C}$$$ for certain positive $$$x$$$, $$$y$$$, $$$z$$$);
  5. ($$$9$$$ points): $$$s_is_{i+1} \ne \texttt{CA}$$$ for $$$1 \le i \lt n$$$;
  6. ($$$10$$$ points): $$$T = 1$$$, $$$n \le 12$$$;
  7. ($$$8$$$ points): $$$n \le 12$$$;
  8. ($$$28$$$ points): $$$K \le 2000$$$;
  9. ($$$30$$$ points): without additional constraints.
Example
Input
2
5
ABCCA
19
CCAABBBABBAAABBCCAA
Output
3
28
Note

In the first set of input data from the first example, no more than $$$3$$$ consecutive operations can be performed on the string ABCCA. One example of how $$$3$$$ consecutive operations can be performed is [ABCCA $$$\rightarrow$$$ BACCA, BACCA $$$\rightarrow$$$ BACAC, BACAC $$$\rightarrow$$$ BAACC].