| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 12882 | Patrick and Spongebob in Tentacle Acres |
|
| 12883 | Patrick and Spongebob in SAO |
|
| 12884 | Patruto and Spongebob run away |
|
Description
Because Squidward’s had enough of living with the “good neighbors”, he moved out of Bikini Bottom. SpongeBob and Patrick wanna apologize to him and persuade him to come back. So they go to Tentacle Acres, where Squidward is living now.
After arrving there, they shortly find out there are a lot of octopuses gathering on the street. Specifically, there are n rows of m octopuses on the street.
Spongebob thinks that Squidward must be one of the octopuses there. But all of them look like Squidward, it’s too hard to find out who is Squidward. Fortunately Patrick brings the book – “How to find out Squidward”.
Thanks to the book, they know Squidward has a big nose. Hence the octopus with a big nose probably is Squidward. Now you are given the size of all the octopuses’ noses. The size of the j-th octopus’s nose in row i is aij. Spongebob and Patrick need you to find out the octopus with the biggest nose from the l-th octopus to the r-th octopus in the row u, row (u+1), …, row d (you only need to output the biggest size).
You have to help Spongebob and Patrick q times.
Subtask
- for testcase 1~2: n = 1, aij = 1
- for testcase 3~5: n = 1
- for testcase 6~10: no additional restriction
Note
You don't need to store all the query(i.e. all the u, d, l, r) and output the answers together in the end. When you get a query, you can just output the answer for the query immediately.
You can reference the following code.
Input
The first line contains two integer n, m (1 ≤ n, m ≤ 100) – the number of rows and the number of octopuses in a row.
The following n lines contain m integers each, the j-th element in the i-th line aij is the size of the j-th octopus's nose in row i (1 ≤ aij ≤ 100).
Next line contain a integer q (1 ≤ q ≤ 100) – the times you have to help Spongebob and Patrick.
Then q lines follow. Each line contains four integer u, d, l, r (1 ≤ u ≤ d ≤ n, 1 ≤ l ≤ r ≤ m) – the range of octopuses you have to find out the biggest size of noses.
Output
For each time you help Spogebob and Patrick, output the biggest size of noses.
Remember to print a newline('\n') at the end of the last line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
UPD(2020/10/12 14:42): We update the description (new part added are in red word) for more clearly. Sorry for the inconvenience.
Spongebob and Patrick finally find out the guy with the biggest nose. But unluckily the guy is not Squidward (actually he is Barnacle Boy).
Suddenly, they see some octopus flies over.
“Well, we know one thing: it sure isn’t that guy.” said Spongebob.
Anyway Patrick is very hungry so they go to the restaurant, SAO(Seafood Around Octopuses), for their dinner. After arrving SAO, they order one Ragout Rabbit first.
They quickly eat up the Ragout Rabbit. But now they're facing a problem: they don’t know what they should order next. Patrick suggests that they could order the dish which is ordered by other customers mostly. So it’s your turn again!
There are n customers in SAO (of course not include Spongebob, Patrick and you) and they are numbered from 1 to n. Each of them orders exactly one dish. The dish ordered by the i-th customer is represented by an integer ai(the dish's number on the menu). You need to tell Spongebob and Patrick which dish is ordered mostly between the l-th, the (l+1)-th, …, the r-th customers. And if there are not only one kind of dish ordered mostly, you just need to output the dish's number which is the smallest between all the dishes ordered mostly in the range.
You have to help Spongebob and Patrick q times.
Subtask
- for testcase 1~2: ai = 1
- for testcase 3~5: ai = 1 or ai = 2
- for testcase 6~10: no additional restriction
Input
The first line contains one integer n (1 ≤ n ≤ 500) – the number of customers in SAO.
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 500) – the number of dish each customer order.
The third line contains one integer q (1 ≤ q ≤ 500) – the times you have to help Spongebob and Patrick.
Then q lines follow. Each line contains two integer l, r (1 ≤ l ≤ r ≤ n) – the range of customers you have to find out the dish ordered mostly.
Output
For each time you help Spogebob and Patrick, output the dish's number which is ordered mostly in the range of customers(if there are not only one kind of dish ordered mostly, you just need to output the dish's number which is the smallest between all the dishes ordered mostly in the range).
Remember to print a newline('\n') at the end of the last line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
After finishing dinner in SAO, it's time to have the bill. But Spongebob only has bubble-money and Patrick only has rock-money.
Of course they can't pay in neither bubble-money nor in rock-money. So the cashier is so mad that he calls the police to catch them. Spongebob and Patrick feel scared and they run away immediately(please don’t imitate them). To prevent from being caught, Patrick decide to cosplay a ninja.
Assuredly Patrick needs to move like a ninja, too. Formally we call "moving like a ninja" is that the footprint he left will form a swirl like the design on the forehead which Patrick put on. And you have to help Patrick to move like a ninja.
To simplify the problem, we consider Patrick is on a 2n x 2n grid. And he is at the upper-left cell (1,1) in the begining. When he starts to move, he will go right continuously until the next cell he will move to is out of bounds or has been visited before. Then he will go down with the same pattern(stops when the next cell is out of bounds or has been visited). Similarly he goes left and goes up with the same pattern. And continue to keep going right, going down, going left, going up, going right, going down… until he can’t move anymore.
What you have to do is to offer a map. And there must be a 2n x 2n grid on the map and all the cells in the grid are noted the order Patrick should visit. In this way Patrick can move like a ninja by following your map(don’t worry about Patrick’s counting ability).
The following image shows the example of n = 3(so the grid is 6 x 6).
Subtask
- for testcase 1: n = 1
- for testcase 2: n = 2
- for testcase 3: n = 3
- for testcase 4: n = 4
- for testcase 5~10: no additional restriction
Input
The first line contains one integer n (1 ≤ n ≤ 250) – the size of the grid which Patrick moves on.
Output
Output a 2n x 2n grid which is the map Patrick will follow.
Please reference the format of sample output and do not output space at the end of any line.
Remember to print a newline('\n') at the end of the last line.