← 返回题目列表

Codeforces · 2036/E

E. 扭转河流

中文机器翻译题面 查看原题

古代圣贤的阴谋决定为了自己的方便改变河流的方向,将世界推向了边缘。但在实施他们的宏伟计划之前,他们决定仔细思考他们的策略——这就是圣人所做的。

有 $$$n$$$ 个国家,每个国家都有 $$$k$$$ 个区域。对于第 $$$i$$$ 个国家的第 $$$j$$$ 个地区,他们计算了值 $$$a_{i,j}$$$,该值反映了该地区的水量。

圣人们打算在第$$$i$$$国家的第$$$j$$$区域和第$$$(i + 1)$$$国家的第$$$j$$$区域之间为所有$$$1 \leq i \leq (n - 1)$$$ 和所有$$$1 \leq j \leq k$$$ 创建通道。

由于所有 $$$n$$$ 国家都位于大斜坡上,因此水流向数字最多的国家。根据先贤的预测,通道系统创建后,第$$$i$$$个国家的第$$$j$$$个区域的新值将是$$$b_{i,j} = a_{1,j} | a_{2,j} | ... | a_{i,j}$$$,其中$$$|$$$表示按位“OR”运算。

在水的重新分配之后,圣人们的目标是选择最适合居住的国家,因此他们会向您发送$$$q$$$查询以供考虑。

每个查询将包含 $$$m$$$ 要求。

每个要求包含三个参数:区域编号 $$$r$$$、符号 $$$o$$$(“$$$<$$$”或“$$$>$$$”)以及值 $$$c$$$。如果 $$$o$$$ = "$$$<$$$",则在您选择的国家/地区的第 $$$r$$$ 区域中,新值必须严格小于限制 $$$c$$$,如果 $$$o$$$ = "$$$>$$$",则它必须严格大于限制。

换句话说,所选国家 $$$i$$$ 必须满足所有 $$$m$$$ 要求。如果在当前要求中$$$o$$$ = "$$$<$$$",则必须满足$$$b_{i,r} < c$$$,并且如果$$$o$$$ = "$$$>$$$",则$$$b_{i,r} > c$$$。

在响应每个查询时,您应该输出一个整数 - 合适国家/地区的编号。如果有多个这样的国家,则输出最小的一个。如果不存在这样的国家,则输出$$$-1$$$。

输入

第一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$q$$$ ($$$1 \leq n, k, q \leq 10^5$$$) — 分别是国家、地区和查询的数量。

接下来有 $$$n$$$ 行,其中第 $$$i$$$ 行包含 $$$k$$$ 整数 $$$a_{i,1}, a_{i,2}, \dots, a_{i,k}$$$ ($$$1 \leq a_{i,j} \leq 10^9$$$),其中$$$a_{i,j}$$$ 是第 $$$i$$$ 个国家/地区的第 $$$j$$$ 个区域的值。

然后,描述$$$q$$$查询。

每个查询的第一行包含一个整数 $$$m$$$ ($$$1 \leq m \leq 10^5$$$) — 需求数量。

然后跟随 $$$m$$$ 行,每行包含一个整数 $$$r$$$、一个字符 $$$o$$$ 和一个整数 $$$c$$$ ($$$1 \leq r \leq k$$$, $$$0 \leq c \leq 2 \cdot 10^9$$$),其中 $$$r$$$ 和 $$$c$$$ 是区域编号和值,$$$o$$$ 是“$$$<$$$”或“$$$>$$$”——符号。

保证 $$$n \cdot k$$$ 不超过 $$$10^5$$$,并且所有查询的 $$$m$$$ 总和也不超过 $$$10^5$$$。

输出

对于每个查询,在新行中输出一个整数 - 合适国家/地区的最小数字,如果不存在这样的国家/地区,则为 $$$-1$$$。

示例

输入 #1

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

输出 #1

2
-1
3
1

注意

在示例中,区域的初始值如下:

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

创建通道后,新值将如下所示:

$$$1$$$$$$3$$$$$$5$$$$$$9$$$$$$1 | 4$$$$$$3 | 6$$$$$$5 | 5$$$$$$9 | 3$$$$$$1 | 4 | 2$$$$$$3 | 6 | 1$$$$$$5 | 5 | 2$$$$$$9 | 3 | 7$$$ $$$\向下箭头$$$ $$$1$$$$$$3$$$$$$5$$$$$$9$$$$$$5$$$$$$7$$$$$$5$$$$$$11$$$$$$7$$$$$$7$$$$$$7$$$$$$15$$$

在第一个查询中,需要输出最小国家编号(即行),其中第一个区域(即列)的水重新分配后,新值将大于 4 且小于 6,而在第二个区域将小于 8。只有编号为 $$$2$$$ 的国家/地区符合​​这些要求。

在第二个查询中,没有符合指定要求的国家/地区。

在第三个查询中,只有编号为 $$$3$$$ 的国家/地区适合。

在第四个查询中,三个国家都满足条件,因此答案是最小的数字$$$1$$$。