Practice on Toph
Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.
Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.
Bob is the owner of a shop named “Color Maker”. He has 256 types of watercolor in his shop. The types are numbered from 0 to 255. Bob stores the watercolors in small boxes. One box contains only one type of watercolor and there can be more than one box containing the same type of watercolor. Bob keeps the boxes on a shelf side by side. As he has a limited supply of watercolors, he sells the boxes of watercolors with a condition applied.
Bob arranges another set of sample boxes containing watercolors and keeps them on another shelf side by side. He does not sell these sample boxes.
After that, Bob numbers the boxes. Let the number of boxes on the first shelf is N and the number of the sample boxes is M. Then Bob numbers the boxes on the first shelf from 1 to N and the sample boxes from 1 to M.
When Alice wants to buy watercolors in this shop, Bob asks her to choose a box. If she chooses the k^{th} box, Bob finds out a position j in the sample boxes and the number of boxes p such that:
B_{k} = S_{j}, B_{k+1} = S_{j+1}, B_{k+2} = S_{j+2},…………..,B_{k+p1} = S_{j+p1}, where B_{i} represents the i^{th} box on the first shelf, S_{i} represents the i^{th} box of the sample boxes and k ≥ 1, k+p1 ≤ N, j ≥ 1 and j+p1 ≤ M. Bob then sells p boxes to Alice.
Surprisingly, Bob notices that there can be multiple ways and multiple values of p possible. Alice demands that among the ways, he has to choose the way in which the value of p is maximized and has to sell p boxes. Since calculating the maximum possible value of p is tough for Alice, she asks you to calculate this on behalf of her.
The first line of the input contains two integers N, M  the number of boxes on the first shelf and the number of the sample boxes.
The second line contains N spaceseparated integers. the i^{th} integer represents the type of the watercolor i^{th} box contains.
The third line contains M spaceseparated integers. the i^{th} integer represents the type of the watercolor i^{th} sample box contains.
The next line contains an integer Q, the number of the queries.
In each of the next Q lines, there will be an integer k, the position of the box Alice chooses.
Constraints:
1 ≤ N ≤ 10^{6}
1 ≤ M ≤ 10^{3}
0 ≤ type of watercolor ≤ 255
1 ≤ Q ≤ 10^{6}
1 ≤ k ≤ N
For each query, print in this format in a single line (without quotes): “Query x: y”, where x is the no. of the query and y is the maximum possible value of p described in the statement.
Input  Output 

6 5 14 25 90 14 81 12 14 14 81 12 0 3 5 2 4  Query 1: 2 Query 2: 0 Query 3: 3 

69% Solution Ratio
tmwilliamlin168Earliest,
EgorKulikovFastest, 0.3s
mahbubcsejuLightest, 27 MB
borisalShortest, 1501B
Login to submit