| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11635 | Position |
|
| 14028 | Max Palindrome Matrix |
|
| 14045 | Final Battle with Penguin07 |
|
Description
Determine the positions of each letter in a given string (with length < 1000001). Then output the positions of each letters in lexicographical order. For each letter, output its positions in increasing order.
For example, “AbAABBCAaa”
A is at position 0, 2, 3, 7; B is at position 4, 5; C is at position 6; a is at position 8, 9; b is at position 1.
Input
There is only one row, and it is a string S with length smaller than 1000001.
Output
Please output the answer according to the above requirements, and remember to add ‘\n’ at the end of the outcome of every letter.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
If a matrix remains the same when rotated 180 degrees, it is referred to as a "palindrome matrix".
Given an n * m matrix, please output the area of the max (largest) palidrome matrix in it.
In sample testcase 1, the max palindrome matrix is:
1 2 3
2 1 2
3 2 1
In sample testcase 2, the max palindrome matrix is:
1 2 3 4
4 3 2 1
You may use the following code to get all possible submatrices for Testcases 6 and 7:
// (x1, y1) means the upper left coordinate
// (x2, y2) means the lower right coordinate
for (int x1 = 0; x1 < n; x1++) {
for (int y1 = 0; y1 < m; y1++) {
for (int x2 = x1; x2 < n; x2++) {
for (int y2 = y1; y2 < m; y2++) {
// your code ...
}
}
}
}
Input
There is an integer T in the first line, representing that you are given T testcases.
In each testcase, the first line contains two integers n and m, and each of the following n lines has m integers, representing the given matrix.
1 <= T <= 10, each number in the matrix is between [1, 1e9]
1 <= n, m <= 40
Testcases 1~3: n = 1
Testcases 4, 5: guaranteed that the answer is a square
Testcases 6, 7: no other restriction
Output
Print the area of the max palidrome matrix in it.
Don't forget to print '\n' in the end.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
After defeating Penguin07 in the Counting Game, you successfully became a Professional Esports Player.
Recently, a new game called “Counting Game 2” has been released on the Steam gaming platform.
Counting Game 2 is significantly more challenging than the original Counting Game and features the following gameplay:
- You are given a table A with N rows and M columns, and there are K operations in total. The operations are as follows:
- For each operation, you are provided with five integers X1,Y1,X2,Y2, and Z. These values represent that you need to add Z to the elements that are located in rows X1 to X2 and columns Y1 to Y2, which can be expressed as Ai,j := Ai,j + Z, for all i in the range [X1,X2] and for all j in the range [Y1,Y2].
- After completing these operations K times, please output the content of table A.
- Finally, there are Q queries, and each query provides you with four integers X1,Y1,X2, and Y2. Your task is to calculate and output the sum of the elements in rows X1 to X2 and columns Y1 to Y2, which is represented as
Please note that the indices for the elements in matrix A are 1-based. Therefore, the ranges for X1,X2,Y1, and Y2 are as follows: 1 ≤ X1 ≤ X2 ≤ N and 1 ≤ Y1 ≤ Y2 ≤ M.
Penguin07, with his brilliant mind, mastered Counting Game 2 as soon as it was released. In each game, he can finish within one second. Penguin07 has challenged you, and if you can defeat him, he will pass on the title of the Ultimate Professional Esports Player to you. As the smartest person in the world, you must win this title.
Input
The first line contains four positive integers: N,M,K,Q, which represent A has N rows and M columns, followed by K operations and, finally, Q queries.
Following this, there are N lines, each containing M integers, denoted as Ai,j, representing the elements of matrix A.
Next, there are K lines, each containing five integers: X1,Y1,X2,Y2,Z, which represent the details of the K operations.
Finally, there are Q lines, each containing four integers: X1,Y1,X2,Y2, representing the content of the Q queries.
Constraints:
- Test Case 1: N = 1, 1 ≤ K ≤ 2 * 106, Q = 0
- Test Case 2: N = 1, 1 ≤ K ≤ 2 * 106, 1 ≤ Q ≤ 103
- Test Cases 3 ~ 5: N = 1, 1 ≤ K, Q ≤ 1.5 * 106
- Test Cases 6 ~ 7: 1 ≤ K, Q ≤ 105
- For all test cases: −109 ≤ A1,1, ... , AN,M, Z ≤ 109, 1 ≤ X1 ≤ X2 ≤ N, 1 ≤ Y1 ≤ Y2 ≤ M, 1 ≤ N, M ≤ 103
Output
Each of the first N lines outputs M integers. These integers represent the content of matrix A after performing K operations.
Following that, there are Q lines, each of which outputs a single integer, representing the answer to the corresponding query.
Do not include any spaces at the end of line.
Remember to print a ‘\n’ at the end of the output.
Hint 1
A usual computer can run 109 basic operations (such as +, -, &, |) in 1 second. Although this depends on the judging server, this number serves as a good estimation for the running time of your code. Try to figure out how much operations your code needs to execute to finish all the computations (since not all operations in your code are basic operations, another estimate criterion is 108 operations (+, -, *, /, =, ...) in 1 second)!
Hint 2
To handle the Q queries efficiently, you can compute another prefix-sum array of A first:
prefix_sum[1] = A[1], prefix_sum[2] = A[1] + A[2], ..., prefix_sum[N] = A[1] + A[2] + ... + A[N].
Sample IO Description
Sample I/O 1:
