← 返回题目列表

AtCoder · abc344_g

G. 要点与比较

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

分数: 625 点

问题陈述

注意特殊的输入格式。

有 N 点 (X_i,Y_i) 在 xy- 平面。您会在输入中获得这些点。

另外, Q 整数对 给出了 (A_j,B_j) 。
定义 f(A_j,B_j) 作为索引的数量 i 满意 Y_i \ge A_j \times X_i + B_j.

查找 \displaystyle \sum^{Q}_{j=1} f(A_j,B_j).

在这里, Q 变得非常大,所以 (A_j,B_j) 没有直接给出。
相反, 给出 G_0, R_a,和 R_b ,并且 (A_j,B_j) 生成如下:

  • 首先,对于 n \ge 0,定义 G_{n+1} = (48271 \times G_n) \mod (2^{31}-1).
  • 对于 j=1,2,\dots,Q,生成 (A_j,B_j) 如下:
    • A_j = -R_a + (G_{3j - 2} \mod (2 \times R_a + 1) )
    • B_j = -R_b + ((G_{3j - 1} \times (2^{31}-1) + G_{3 j}) \mod (2 \times R_b + 1) )

从这个方法可以看出 A_j 和 B_j 满足以下约束:

  • -R_a \le A_j \le R_a
  • -R_b \le B_j \le R_b

约束

  • 所有输入值均为整数。
  • 1 \le N \le 5000
  • 1 \le Q \le 10^7
  • |X_i|, |Y_i| \le 10^8
  • 对 (X_i,Y_i) 是不同的。
  • 0 \le G_0 < (2^{31}-1)
  • 0 \le R_a \le 10^8
  • 0 \le R_b \le 10^{16}

输入

输入由标准输入按以下格式给出:

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
Q
G_0 R_a R_b

输出

将答案打印为整数。


示例输入 1

7
2 -2
-1 -2
0 1
2 1
-2 2
1 2
0 -1
10
1 5 5

示例输出 1

36

此输入包含十个问题。
生成的 (A_j,B_j) 是 (-2,4),(0,2),(-4,-2),(4,-5),(3,1),(-1,3),(2,-5),(3,-1),(3,5),(3,-2).