Back To School '16: Contest Practice

View as PDF

Submit solution

All submissions

Best submissions

Points: 20 (partial)

Time limit: 1.8s

Memory limit: 256M

Author:

Problem types

In addition to regular schoolwork, jlsajfj frequently visits a website where programmers can practice writing algorithms. This website has an extensive list of classical problems which leaves most aspiring programmers satisfied. jlsajfj's favourite part of the website is the unconventional contest system.

Every month, the website hosts a contest with $P$ $P$ problems. Every problem in this contest has $Q$ $Q$ possible scores, which are integers from $0$ $0$ to $Q-1$ $Q - 1$ inclusive. Obviously, a competitor receives exactly one final score for a single problem. A scoring distribution is a sequence of $P$ $P$ integers where the $i^{th}$ $i^{t h}$ integer is the user's score on the $i^{th}$ $i^{t h}$ problem.

User Y is equal or better than user Z when, for each of the $P$ $P$ problems, user Y has an equal or better score than user Z. A user's improvement index is the number of equal or better participants. This includes oneself, since nobody should have an improvement index of $0$ $0$ !

jlsajfj convinced a friend, Shinigami, to try out an amazing contest. However, the website prevents users from knowing the leaderboard position during the contest, as this may influence the users' performance, and further, the website normally posts the results one week later. This does not stop jlsajfj from discovering and accessing the well-hidden database on the website. This database contains the scoring distributions of all $N$ $N$ users.

Both jlsajfj and Shinigami want to be famous for implementing a system where you can check your improvement index, so they split the work (fairly unevenly). jlsajfj successfully builds a program which determines whether a specific scoring distribution occurred in the contest. But Shinigami is stuck trying to calculate the improvement index of a user. In total, there are $X$ $X$ valid queries sent to the system at the same time. Help Shinigami with his work!

Input Specification

The first line contains the integers $P$ $P$ $(1 \le P \le 20)$ $(1 \leq P \leq 20)$ , $Q$ $Q$ $(2 \le Q \le 20)$ $(2 \leq Q \leq 20)$ and $N$ $N$ $(1 \le N \le 50\,000)$ $(1 \leq N \leq 50 000)$ . It is guaranteed that $2 \le Q^P \le 200\,000$ $2 \leq Q^{P} \leq 200 000$ .

The following $N$ $N$ lines contain a scoring distribution (described above).

The next line contains $X$ $X$ $(1 \le X \le 50\,000)$ $(1 \leq X \leq 50 000)$ , the number of queries that Shinigami must process.

In each of the next $X$ $X$ lines, there is a scoring distribution. One of the $N$ $N$ users is guaranteed to have this distribution.

Output Specification

For each of the $X$ $X$ queries, output the improvement index of the user who had this scoring distribution.

Constraints

Subtask 1 [25%]

$N \le 500$ $N \leq 500$

Subtask 2 [25%]

$P \le 2$ $P \leq 2$

Subtask 3 [50%]

No additional constraints.

Sample Input

Copy

4 11 5
10 10 10 10
10 10 2 5
10 9 5 0
0 10 0 0
0 0 0 0
6
10 10 10 10
10 10 2 5
10 9 5 0
0 10 0 0
0 0 0 0
10 9 5 0

Sample Output

Copy

Comments

-3

septence123 commented on Jan. 20, 2017, 12:40 a.m.

Why does 10 10 2 5 have the same improvement index of 10 9 5 0? Can someone explain?

-26

jlsajfj commented on Jan. 14, 2017, 8:35 p.m.

Who is Shinigami?

This comment is hidden due to too much negative feedback. Show it anyway.

-54

Kirito commented on Sept. 16, 2016, 7:18 p.m. ← edit 2 →

TFW u finally solve the problem featuring you a year later.

Downvotes go here.

This comment is hidden due to too much negative feedback. Show it anyway.

-54

jlsajfj commented on Sept. 17, 2016, 1:27 a.m.

i want downvotes too :(

This comment is hidden due to too much negative feedback. Show it anyway.

-35

kobortor commented on Oct. 15, 2016, 5:36 p.m.

I want upvotes too.

This comment is hidden due to too much negative feedback. Show it anyway.