yl-9/probench huggingface dataset:
# Stalin Sort

## Problem Description

Stalin Sort is a humorous sorting algorithm designed to eliminate elements which are out of place instead of bothering to sort them properly, lending itself to an $ \mathcal{O}(n) $ time complexity.

It goes as follows: starting from the second element in the array, if it is strictly smaller than the previous element (ignoring those which have already been deleted), then delete it. Continue iterating through the array until it is sorted in non-decreasing order. For example, the array $ [1, 4, 2, 3, 6, 5, 5, 7, 7] $ becomes $ [1, 4, 6, 7, 7] $ after a Stalin Sort.

We define an array as vulnerable if you can sort it in non-increasing order by repeatedly applying a Stalin Sort to any of its subarrays $ ^{\text{∗}} $ , as many times as is needed.

Given an array $ a $ of $ n $ integers, determine the minimum number of integers which must be removed from the array to make it vulnerable.

 $ ^{\text{∗}} $ An array $ a $ is a subarray of an array $ b $ if $ a $ can be obtained from $ b $ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

## Input Format

Each test consists of several test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 500 $ ) — the number of test cases. This is followed by descriptions of the test cases.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2000 $ ) — the size of the array.

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ).

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2000 $ .

## Output Format

For each test case, output a single integer — the minimum number of integers which must be removed from the array to make it vulnerable.

## Sample #1

### Sample Input #1

```
6
7
3 6 4 9 2 5 2
5
5 4 4 2 2
8
2 2 4 4 6 6 10 10
1
1000
9
6 8 9 10 12 9 7 5 4
7
300000000 600000000 400000000 900000000 200000000 400000000 200000000
```

### Sample Output #1

```
2
0
6
0
4
2
```

## Hint

In the first test case, the optimal answer is to remove the numbers $ 3 $ and $ 9 $ . Then we are left with $ a = [6, 4, 2, 5, 2] $ . To show this array is vulnerable, we can first apply a Stalin Sort on the subarray $ [4, 2, 5] $ to get $ a = [6, 4, 5, 2] $ and then apply a Stalin Sort on the subarray $ [6, 4, 5] $ to get $ a = [6, 2] $ , which is non-increasing.

In the second test case, the array is already non-increasing, so we don't have to remove any integers.

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: brute force, greedy
Difficulty: 1100
# Rectangle Arrangement

## Problem Description

You are coloring an infinite square grid, in which all cells are initially white. To do this, you are given $ n $ stamps. Each stamp is a rectangle of width $ w_i $ and height $ h_i $ .

You will use each stamp exactly once to color a rectangle of the same size as the stamp on the grid in black. You cannot rotate the stamp, and for each cell, the stamp must either cover it fully or not cover it at all. You can use the stamp at any position on the grid, even if some or all of the cells covered by the stamping area are already black.

What is the minimum sum of the perimeters of the connected regions of black squares you can obtain after all the stamps have been used?

## Input Format

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 500 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 100 $ ).

The $ i $ -th of the next $ n $ lines contains two integers $ w_i $ and $ h_i $ ( $ 1 \le w_i, h_i \le 100 $ ).

## Output Format

For each test case, output a single integer — the minimum sum of the perimeters of the connected regions of black squares you can obtain after all the stamps have been used.

## Sample #1

### Sample Input #1

```
5
5
1 5
2 4
3 3
4 2
5 1
3
2 2
1 1
1 2
1
3 2
3
100 100
100 100
100 100
4
1 4
2 3
1 5
3 2
```

### Sample Output #1

```
20
8
10
400
16
```

## Hint

In the first test case, the stamps can be used as shown on the left. Each stamp is highlighted in its own color for clarity.

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2027A/eb6eb9753bb0b7d5590d43612099263639e3e940.png)After all these stamps are used, there is one black region (as shown on the right), and its perimeter is $ 20 $ . It can be shown that there is no way of using the stamps that yields a lower total perimeter.

In the second test case, the second and third stamps can be used entirely inside the first one, so the minimum perimeter is equal to $ 8 $ .

## Limit



Time Limit
1.00s

Memory Limit
250.00MB

Tags: geometry, implementation, math
Difficulty: 800
# Bermart Ice Cream

## Problem Description

In the Bermart chain of stores, a variety of ice cream is sold. Each type of ice cream has two parameters: price and tastiness.

Initially, there is one store numbered $ 1 $ , which sells nothing. You have to process $ q $ queries of the following types:

- $ 1~x $ — a new store opens, that sells the same types of ice cream as store $ x $ . It receives the minimum available positive index. The order of the types of ice cream in the new store is the same as in store $ x $ .
- $ 2~x~p~t $ — a type of ice cream with price $ p $ and tastiness $ t $ becomes available in store $ x $ .
- $ 3~x $ — a type of ice cream that was available the longest (appeared the earliest) in store $ x $ is removed.
- $ 4~x~p $ — for store $ x $ , find the maximum total tastiness of a subset of types of ice cream that are sold there, such that the total price does not exceed $ p $ (each type can be used in the subset no more than once).

## Input Format

The first line contains a single integer $ q $ ( $ 1 \le q \le 3 \cdot 10^4 $ ) — the number of queries.

Each of the following $ q $ lines contains a query in the format described in the statement:

- $ 1~x $ ;
- $ 2~x~p~t $ ( $ 1 \le p, t \le 2000 $ );
- $ 3~x $ ;
- $ 4~x~p $ ( $ 1 \le p \le 2000 $ ).

Additional constraints on the input data:

- $ x $ in each query does not exceed the current number of stores (that is, $ 1 $ plus the number of type $ 1 $ queries);
- query type $ 3 $ is not applied to a store that has no types of ice cream;
- there is at least one query of type $ 4 $ .

## Output Format

For each query of type $ 4 $ , output a single integer — for store $ x $ , find the maximum total tastiness of a subset of types of ice cream that are sold there, such that the total price does not exceed $ p $ (each type can be used in the subset no more than once).

## Sample #1

### Sample Input #1

```
12
2 1 5 7
2 1 3 4
4 1 4
4 1 8
4 1 2
1 1
2 2 4 10
4 1 9
4 2 9
3 1
4 1 9
4 2 9
```

### Sample Output #1

```
4
11
0
11
17
4
17
```

## Limit



Time Limit
2.00s

Memory Limit
1000.00MB

Tags: data structures, dfs and similar, divide and conquer, dp, implementation, trees
Difficulty: 2700
# Best Subsequence

## Problem Description

Given an integer array $ a $ of size $ n $ .

Let's define the value of the array as its size minus the number of set bits in the bitwise OR of all elements of the array.

For example, for the array $ [1, 0, 1, 2] $ , the bitwise OR is $ 3 $ (which contains $ 2 $ set bits), and the value of the array is $ 4-2=2 $ .

Your task is to calculate the maximum possible value of some subsequence of the given array.

## Input Format

The first line contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 100 $ ).

The second line of each test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i < 2^{60} $ ).

## Output Format

For each test case, print the maximum possible value of some subsequence of the given array.

## Sample #1

### Sample Input #1

```
4
3
0 0 0
4
1 0 1 2
1
5
8
7 1 48 14 13 8 7 6
```

### Sample Output #1

```
3
2
0
3
```

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: bitmasks, dfs and similar, flows, graph matchings, graphs
Difficulty: 2500
# Sums of Segments

## Problem Description

You are given a sequence of integers $ [a_1, a_2, \dots, a_n] $ . Let $ s(l,r) $ be the sum of elements from $ a_l $ to $ a_r $ (i. e. $ s(l,r) = \sum\limits_{i=l}^{r} a_i $ ).

Let's construct another sequence $ b $ of size $ \frac{n(n+1)}{2} $ as follows: $ b = [s(1,1), s(1,2), \dots, s(1,n), s(2,2), s(2,3), \dots, s(2,n), s(3,3), \dots, s(n,n)] $ .

For example, if $ a = [1, 2, 5, 10] $ , then $ b = [1, 3, 8, 18, 2, 7, 17, 5, 15, 10] $ .

You are given $ q $ queries. During the $ i $ -th query, you are given two integers $ l_i $ and $ r_i $ , and you have to calculate $ \sum \limits_{j=l_i}^{r_i} b_j $ .

## Input Format

The first line contains one integer $ n $ ( $ 1 \le n \le 3 \cdot 10^5 $ ).

The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ -10 \le a_i \le 10 $ ).

The third line contains one integer $ q $ ( $ 1 \le q \le 3 \cdot 10^5 $ ).

Then $ q $ lines follow, the $ i $ -th of them contains two integers $ l_i $ and $ r_i $ ( $ 1 \le l_i \le r_i \le \frac{n(n+1)}{2} $ ).

## Output Format

Print $ q $ integers, the $ i $ -th of which should be equal to $ \sum \limits_{j=l_i}^{r_i} b_j $ .

## Sample #1

### Sample Input #1

```
4
1 2 5 10
15
1 1
1 2
1 3
1 4
1 5
1 10
5 10
6 10
2 8
3 4
3 10
3 8
5 6
5 5
1 8
```

### Sample Output #1

```
1
4
12
30
32
86
56
54
60
26
82
57
9
2
61
```

## Limit



Time Limit
4.00s

Memory Limit
500.00MB

Tags: binary search, data structures, dp, implementation, math
Difficulty: 1900
# Action Figures

## Problem Description

There is a shop that sells action figures near Monocarp's house. A new set of action figures will be released shortly; this set contains $ n $ figures, the $ i $ -th figure costs $ i $ coins and is available for purchase from day $ i $ to day $ n $ .

For each of the $ n $ days, Monocarp knows whether he can visit the shop.

Every time Monocarp visits the shop, he can buy any number of action figures which are sold in the shop (of course, he cannot buy an action figure that is not yet available for purchase). If Monocarp buys at least two figures during the same day, he gets a discount equal to the cost of the most expensive figure he buys (in other words, he gets the most expensive of the figures he buys for free).

Monocarp wants to buy exactly one $ 1 $ -st figure, one $ 2 $ -nd figure, ..., one $ n $ -th figure from the set. He cannot buy the same figure twice. What is the minimum amount of money he has to spend?

## Input Format

The first line contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.

Each test case consists of two lines:

- the first line contains one integer $ n $ ( $ 1 \le n \le 4 \cdot 10^5 $ ) — the number of figures in the set (and the number of days);
- the second line contains a string $ s $ ( $ |s| = n $ , each $ s_i $ is either 0 or 1). If Monocarp can visit the shop on the $ i $ -th day, then $ s_i $ is 1; otherwise, $ s_i $ is 0.

Additional constraints on the input:

- in each test case, $ s_n $ is 1, so Monocarp is always able to buy all figures during the $ n $ -th day;
- the sum of $ n $ over all test cases does not exceed $ 4 \cdot 10^5 $ .

## Output Format

For each test case, print one integer — the minimum amount of money Monocarp has to spend.

## Sample #1

### Sample Input #1

```
4
1
1
6
101101
7
1110001
5
11111
```

### Sample Output #1

```
1
8
18
6
```

## Hint

In the first test case, Monocarp buys the $ 1 $ -st figure on the $ 1 $ -st day and spends $ 1 $ coin.

In the second test case, Monocarp can buy the $ 1 $ -st and the $ 3 $ -rd figure on the $ 3 $ -rd day, the $ 2 $ -nd and the $ 4 $ -th figure on the $ 4 $ -th day, and the $ 5 $ -th and the $ 6 $ -th figure on the $ 6 $ -th day. Then, he will spend $ 1+2+5=8 $ coins.

In the third test case, Monocarp can buy the $ 2 $ -nd and the $ 3 $ -rd figure on the $ 3 $ -rd day, and all other figures on the $ 7 $ -th day. Then, he will spend $ 1+2+4+5+6 = 18 $ coins.

## Limit



Time Limit
2.50s

Memory Limit
500.00MB

Tags: binary search, brute force, constructive algorithms, data structures, greedy, implementation
Difficulty: 1500
# Black Cells

## Problem Description

You are given a strip divided into cells, numbered from left to right from $ 0 $ to $ 10^{18} $ . Initially, all cells are white.

You can perform the following operation: choose two white cells $ i $ and $ j $ , such that $ i \ne j $ and $ |i - j| \le k $ , and paint them black.

A list $ a $ is given. All cells from this list must be painted black. Additionally, at most one cell that is not in this list can also be painted black. Your task is to determine the minimum value of $ k $ for which this is possible.

## Input Format

The first line contains a single integer $ t $ ( $ 1 \le t \le 500 $ ) — the number of test cases.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2000 $ ).

The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0 < a_i < 10^{18} $ ; $ a_i < a_{i + 1} $ ).

Additional constraint on the input: the sum of $ n $ across all test cases does not exceed $ 2000 $ .

## Output Format

For each test case, print a single integer — the minimum value of $ k $ for which it is possible to paint all the given cells black.

## Sample #1

### Sample Input #1

```
4
2
1 2
1
7
3
2 4 9
5
1 5 8 10 13
```

### Sample Output #1

```
1
1
2
3
```

## Hint

In the first example, with $ k=1 $ , it is possible to paint the cells $ (1, 2) $ .

In the second example, with $ k=1 $ , it is possible to paint the cells $ (7, 8) $ .

In the third example, with $ k=2 $ , it is possible to paint the cells $ (2, 4) $ and $ (8, 9) $ .

In the fourth example, with $ k=3 $ , it is possible to paint the cells $ (0, 1) $ , $ (5, 8) $ and $ (10, 13) $ .

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: binary search, brute force, constructive algorithms, greedy
Difficulty: 1300
# Perpendicular Segments

## Problem Description

You are given a coordinate plane and three integers $ X $ , $ Y $ , and $ K $ . Find two line segments $ AB $ and $ CD $ such that

1. the coordinates of points $ A $ , $ B $ , $ C $ , and $ D $ are integers;
2. $ 0 \le A_x, B_x, C_x, D_x \le X $ and $ 0 \le A_y, B_y, C_y, D_y \le Y $ ;
3. the length of segment $ AB $ is at least $ K $ ;
4. the length of segment $ CD $ is at least $ K $ ;
5. segments $ AB $ and $ CD $ are perpendicular: if you draw lines that contain $ AB $ and $ CD $ , they will cross at a right angle.

Note that it's not necessary for segments to intersect. Segments are perpendicular as long as the lines they induce are perpendicular.

## Input Format

The first line contains a single integer $ t $ ( $ 1 \le t \le 5000 $ ) — the number of test cases. Next, $ t $ cases follow.

The first and only line of each test case contains three integers $ X $ , $ Y $ , and $ K $ ( $ 1 \le X, Y \le 1000 $ ; $ 1 \le K \le 1414 $ ).

Additional constraint on the input: the values of $ X $ , $ Y $ , and $ K $ are chosen in such a way that the answer exists.

## Output Format

For each test case, print two lines. The first line should contain $ 4 $ integers $ A_x $ , $ A_y $ , $ B_x $ , and $ B_y $ — the coordinates of the first segment.

The second line should also contain $ 4 $ integers $ C_x $ , $ C_y $ , $ D_x $ , and $ D_y $ — the coordinates of the second segment.

If there are multiple answers, print any of them.

## Sample #1

### Sample Input #1

```
4
1 1 1
3 4 1
4 3 3
3 4 4
```

### Sample Output #1

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

## Hint

The answer for the first test case is shown below:

 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2026A/ec912df39bb0649b8cac618bfc67861cbe33f3a9.png)  The answer for the second test case:  ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2026A/16297a765040b390fcf117cbdd6958cb27cfd2f6.png)  The answer for the third test case:  ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2026A/2fa935fca6647221cd973d5ea3b266eb1839dab4.png)  The answer for the fourth test case:  ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF2026A/41df202ce65e0906ba528f2a40ffbcdc5a825158.png)

## Limit



Time Limit
2.00s

Memory Limit
250.00MB

Tags: constructive algorithms, geometry, greedy, math
Difficulty: 900
# Choose Your Queries

## Problem Description

You are given an array $ a $ , consisting of $ n $ integers (numbered from $ 1 $ to $ n $ ). Initially, they are all zeroes.

You have to process $ q $ queries. The $ i $ -th query consists of two different integers $ x_i $ and $ y_i $ . During the $ i $ -th query, you have to choose an integer $ p $ (which is either $ x_i $ or $ y_i $ ) and an integer $ d $ (which is either $ 1 $ or $ -1 $ ), and assign $ a_p = a_p + d $ .

After each query, every element of $ a $ should be a non-negative integer.

Process all queries in such a way that the sum of all elements of $ a $ after the last query is the minimum possible.

## Input Format

The first line contains two integers $ n $ and $ q $ ( $ 2 \le n \le 3 \cdot 10^5 $ ; $ 1 \le q \le 3 \cdot 10^5 $ ) — the number of elements in $ a $ and the number of queries, respectively.

Then $ q $ lines follow. The $ i $ -th of these lines contains two integers $ x_i $ and $ y_i $ ( $ 1 \le x_i, y_i \le n $ ; $ x_i \ne y_i $ ) — the description of the $ i $ -th query.

## Output Format

For each query, print a line containing two characters:

- the first character should be x if you choose $ p=x_i $ , or y if you choose $ p=y_i $ ;
- the second character should be + if you choose $ d=1 $ , or - if you choose $ d=-1 $ .

If there are multiple answers, print any of them.

## Sample #1

### Sample Input #1

```
3 4
1 2
3 2
3 1
1 2
```

### Sample Output #1

```
y+
x+
x-
y-
```

## Sample #2

### Sample Input #2

```
4 4
1 2
2 3
3 4
3 2
```

### Sample Output #2

```
y+
y+
x-
y-
```

## Sample #3

### Sample Input #3

```
4 2
2 1
4 3
```

### Sample Output #3

```
y+
x+
```

## Limit



Time Limit
3.00s

Memory Limit
500.00MB

Tags: constructive algorithms, dfs and similar, dp, graphs, greedy, trees
Difficulty: 2700
# Card Game

## Problem Description

In the most popular card game in Berland, a deck of $ n \times m $ cards is used. Each card has two parameters: suit and rank. Suits in the game are numbered from $ 1 $ to $ n $ , and ranks are numbered from $ 1 $ to $ m $ . There is exactly one card in the deck for each combination of suit and rank.

A card with suit $ a $ and rank $ b $ can beat a card with suit $ c $ and rank $ d $ in one of two cases:

- $ a = 1 $ , $ c \ne 1 $ (a card of suit $ 1 $ can beat a card of any other suit);
- $ a = c $ , $ b > d $ (a card can beat any other card of the same suit but of a lower rank).

Two players play the game. Before the game starts, they receive exactly half of the deck each. The first player wins if for every card of the second player, he can choose his card that can beat it, and there is no card that is chosen twice (i. e. there exists a matching of the first player's cards with the second player's cards such that in each pair the first player's card beats the second player's card). Otherwise, the second player wins.

Your task is to calculate the number of ways to distribute the cards so that the first player wins. Two ways are considered different if there exists a card such that in one way it belongs to the first player and in the other way it belongs to the second player. The number of ways can be very large, so print it modulo $ 998244353 $ .

## Input Format

The only line contains two integers $ n $ and $ m $ ( $ 1 \le n, m \le 500 $ ).

Additional constraint on the input: $ m $ is even.

## Output Format

Print a single integer — the number of ways to distribute the cards so that the first player wins, taken modulo $ 998244353 $ .

## Sample #1

### Sample Input #1

```
1 4
```

### Sample Output #1

```
2
```

## Sample #2

### Sample Input #2

```
2 2
```

### Sample Output #2

```
2
```

## Sample #3

### Sample Input #3

```
3 6
```

### Sample Output #3

```
1690
```

## Sample #4

### Sample Input #4

```
5 4
```

### Sample Output #4

```
568
```

## Sample #5

### Sample Input #5

```
500 500
```

### Sample Output #5

```
84693741
```

## Limit



Time Limit
2.00s

Memory Limit
500.00MB

Tags: combinatorics, dp, fft, greedy, math
Difficulty: 2200
# Attribute Checks

## Problem Description

Imagine a game where you play as a character that has two attributes: "Strength" and "Intelligence", that are at zero level initially.

During the game, you'll acquire $ m $ attribute points that allow you to increase your attribute levels — one point will increase one of the attributes by one level. But sometimes, you'll encounter a so-called "Attribute Checks": if your corresponding attribute is high enough, you'll pass it; otherwise, you'll fail it.

Spending some time, you finally prepared a list which contains records of all points you got and all checks you've met. And now you're wondering: what is the maximum number of attribute checks you can pass in a single run if you'd spend points wisely?

Note that you can't change the order of records.

## Input Format

The first line contains two integers $ n $ and $ m $ ( $ 1 \le m \le 5000 $ ; $ m < n \le 2 \cdot 10^6 $ ) — the number of records in the list and the total number of points you'll get during the game.

The second line contains $ n $ integers $ r_1, r_2, \dots, r_n $ ( $ -m \le r_i \le m $ ), where $ r_i $ encodes the $ i $ -th record:

- If $ r_i = 0 $ , then the $ i $ -th record is an acquiring one attribute point. You can spend to level up either Strength or Intelligence;
- If $ r_i > 0 $ , then it's an Intelligence check: if your Intelligence level is greater than or equal to $ |r_i| $ , you pass.
- If $ r_i < 0 $ , then it's a Strength check: if your Strength level is greater than or equal to $ |r_i| $ , you pass.

Additional constraint on the input: the sequence $ r_1, r_2, \dots, r_n $ contains exactly $ m $ elements equal to $ 0 $ .

## Output Format

Print one integer — the maximum number of checks you can pass.

## Sample #1

### Sample Input #1

```
10 5
0 1 0 2 0 -3 0 -4 0 -5
```

### Sample Output #1

```
3
```

## Sample #2

### Sample Input #2

```
3 1
1 -1 0
```

### Sample Output #2

```
0
```

## Sample #3

### Sample Input #3

```
9 3
0 0 1 0 2 -3 -2 -2 1
```

### Sample Output #3

```
4
```

## Hint

In the first test, it's optimal to spend each point in Strength, so you'll fail $ 2 $ Intelligence checks but pass $ 3 $ Strength checks.

In the second test, you'll fail both checks, since the first point you get comes after the checks.

In the third test, one of the optimal strategies is:

1. spend the first point on Intelligence;
2. spend the second point on Strength;
3. spend the third point on Strength;

 As a result, you'll pass $ 2 $ Intelligence checks $ r_3 $ and $ r_9 $ and $ 2 $ Strength checks $ r_7 $ and $ r_8 $ .

## Limit



Time Limit
2.50s

Memory Limit
500.00MB

Tags: brute force, data structures, dp, implementation, math, two pointers
Difficulty: 1800