103446: [Atcoder]ABC344 G - Points and Comparison
Description
Score: $625$ points
Problem Statement
Pay attention to the special input format.
There are $N$ points $(X_i,Y_i)$ in the $xy$-plane. You are given these points in the input.
Also, $Q$ pairs of integers $(A_j,B_j)$ are given.
Define $f(A_j,B_j)$ as the number of indices $i$ satisfying $Y_i \ge A_j \times X_i + B_j$.
Find $\displaystyle \sum^{Q}_{j=1} f(A_j,B_j)$.
Here, $Q$ gets very large, so $(A_j,B_j)$ are not given directly.
Instead, $G_0$, $R_a$, and $R_b$ are given, and $(A_j,B_j)$ are generated as follows:
- First, for $n \ge 0$, define $G_{n+1} = (48271 \times G_n) \mod (2^{31}-1)$.
- For $j=1,2,\dots,Q$, generate $(A_j,B_j)$ as follows:
- $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) )$
From this method, it can be shown that $A_j$ and $B_j$ satisfy the following constraints:
- $-R_a \le A_j \le R_a$
- $-R_b \le B_j \le R_b$
Constraints
- All input values are integers.
- $1 \le N \le 5000$
- $1 \le Q \le 10^7$
- $|X_i|, |Y_i| \le 10^8$
- The pairs $(X_i,Y_i)$ are distinct.
- $0 \le G_0 < (2^{31}-1)$
- $0 \le R_a \le 10^8$
- $0 \le R_b \le 10^{16}$
Input
The input is given from Standard Input in the following format:
$N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_N$ $Y_N$ $Q$ $G_0$ $R_a$ $R_b$
Output
Print the answer as an integer.
Sample Input 1
7 2 -2 -1 -2 0 1 2 1 -2 2 1 2 0 -1 10 1 5 5
Sample Output 1
36
This input contains ten questions.
The generated $(A_j,B_j)$ are $(-2,4),(0,2),(-4,-2),(4,-5),(3,1),(-1,3),(2,-5),(3,-1),(3,5),(3,-2)$.
Input
Output
问题描述
请注意特殊的输入格式。
在$x-y$平面上有$N$个点$(X_i,Y_i)$。这些点在输入中给出。
此外,给出$Q$对整数$(A_j,B_j)$。
定义$f(A_j,B_j)$为满足$Y_i \ge A_j \times X_i + B_j$的下标$i$的数量。
找到$\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
该输入包含10个问题。
生成的$(A_j,B_j)$为$(-2,4),(0,2),(-4,-2),(4,-5),(3,1),(-1,3),(2,-5),(3,-1),(3,5),(3,-2)$。