| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 12022 | prefix sum |
|
| 14444 | Big orange cat's puzzle |
|
Description
Given a series of numbers, e1, e2, e3, ..., eN.
With these numbers, we want to know what the sum is in some consecutive range.
In every testcase, you will be given M queries.
Each of them contains two integers which represent left bound (L) and right bound (R) respectively.
Your mission is to give the result of eL + eL+1 + ... + eR,
-
Hint 0 : If you get WA for testcase 1, sample input and output might help you.
Hint 1 : If you get TLE for next three testcases, you should think how to decrease some redundant operations for calculations. Try to store other useful information in the array, instead of sum up all the elements for every query! You may search for the problem's title: "prefix sum".
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 : If you get MLE, you have to reduce the size of array you created and decide what exactly should be in the array.
Input
First line contains one integer N which is the size of elements.
Second line will have N integers representing all elements in the testcase.
Third line contains one integer M which is the number of queries.
For following M lines, each line contains exactly two integers that stand for left bound (L) and right bound (R) respectively.
It is guaranteed that:
1. 10 ≦ N ≦ 1,000,000
2. 0 ≦ ei ≦ 100,000, for 1 ≦ i ≦ N
3. L must be less than or equal to R, and R won't exceed the size of elements.
Output
For each query, just give the answer in one line.
Also, remember to print '\n' in the end of line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Big Orange Cat（大橘） loves doing puzzles. He has n types of puzzles in total, and each puzzle i can be represented by a string Ai composed of all visible characters from the ASCII code.
Unfortunately, he messed up the puzzles, what a baganono... Now for each puzzle i, he has found some puzzle pieces, represented by a string Bi. Your task is to find a way to tell Big Orange Cat from which positions in Bi he should take out puzzle pieces and rearrange them to form Ai.
However, there might be many possible ways, and since Big Orange Cat is very lazy, please output the lexicographically smallest method.
Important: The method for comparing the lexicographic order of two strings is as follows: Starting from the first position (leftmost), find the first character that differs. The string with the smaller character at that position is considered lexicographically smaller. For example, "abc" < "abd" because the first differing letter 'c' < 'd'.
Input
The first line of input contains an integer n. n represents the number of puzzle-instruction manual pairs.
The following n lines each contain two strings, Ai and Bi, separated by a space. They represent the i-th puzzle and instruction manual, respectively.
Constraints
- 1 ≤ n ≤ 500
- All strings are composed of uppercase and lowercase letters, and any visible symbols that can be represented by ASCII code (ASCII Codes 33 to 126)
- 1 ≤ | Ai | ≤ | Bi | ≤ 10000 (| S | represents the length of string S)
Subtasks
- Testcases 1 ~ 2: | Ai | = | Bi |, characters within Ai , Bi are arranged in ascending lexicographic order.
- Testcases 3 ~ 4: | Ai | = | Bi |
- Testcases 5 ~ 8: For each Bi, there is only one possible way, or no way at all, to create the corresponding Ai.
- Testcases 9 ~ 10: No additional restrictions.
Tips: ASCII Codes 33 ~ 126 are: !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
Output
Output n lines, each line should be in one of the following two formats according to the situation:
- If Bi can form Ai : Output |Ai| increasing numbers representing the answer (x1 < x2 < ...), separated by a space.
- Output
"baganono"(without quotation marks)
Please remember to print "\n" at the end, and dont print space (" ") at the end of every line.
hint 1: The key to finding the lexicographically smallest solution lies in Big Orange Cat's personality: laziness. Therefore, the secret is to take the smallest possible numbers.
hint 2: Try to recall how you determined whether it was possible to form the required string in homework 4.