UOJ Logo

NOI.AC

1S 512MB

#36. 列队

统计

A. 列队

题目描述

快开学了,小W正在军训。

他们班一共有 $n * m$ 位同学,于是列队的时候,教官让他们站成了 $n$ 排 $m$ 列。小W发现,如果一个人的身高在他所在的那一排是最高的,在那一列也是最高的,那么他会很显眼。由于列队过于无聊,小W开始计算有多少人非常显眼。

这显然难不倒他,于是他想计算有多少人是他所在排第 $x$ 高的,在他所在列是第 $y$ 高的。小W要忙着应付教官了,所以他没有时间来算了,于是他找来了没在军训的你帮他算一算。他可能有很多询问,你需要快速回答所有的询问。

输入格式

第一行三个整数 $n$,$m$,$q$。

接下来 $n$ 行,每行 $m$ 个整数,代表第 $i$ 行第 $j$ 列的整数 $h_{i,j}$ 表示第 $i$ 排第 $j$ 列的人的身高。保证 $[1,n * m]$ 的每个整数出现且仅出现一次。

接下来 $q$ 行,每行两个整数 $x$,$y$,表示一组询问。

输出格式

输出共 $q$ 行,每行一个整数,表示第 $i$ 组询问的答案。

样例1

input

3 3 2
1 8 9
3 2 7
6 5 4
3 3
2 2

output

3
2

explanation

对于第一组询问,$(1,1), (2,2), (3,3)$ 是符合条件的。

样例2

input

3 3 2
1 2 7
6 4 5
8 3 9
3 2
2 3

output

1
2

样例3

见下载文件。

限制与约定

对于 $10\%$ 的数据,$n, m, q \le 100$。

对于另外 $15\%$ 的数据,$n, m \le 100, q \le 10^5$。

对于另外 $20\%$ 的数据,$n, m, q, \le 400$。

对于另外 $5\%$ 的数据,满足 $a_{i,j} = ( i - 1 ) * m + j$。

对于 $100\%$ 的数据,$n, m \le 1000, q \le 5 * 10^5$。

时间限制:1s

空间限制:512MB

下载

样例数据下载