JOI '20 Spring Camp Day 3 P2 - Harvest - DMOJ: Modern Online Judge

JOI '20 Spring Camp Day 3 P2 - Harvest

Points: 35 (partial)

Time limit: 3.0s

Memory limit: 512M

Problem type

IOI Farm is an agricultural farm growing apples. It is famous for being located around a large circular lake.

In IOI Farm, there are $N$ ~N~ employees, numbered from $1$ ~1~ to $N$ ~N~. There are $M$ ~M~ apple trees, numbered from $1$ ~1~ to $M$ ~M~. The perimeter of the lake is $L$ ~L~ meters.

In the beginning, the employee $i$ ~i~ $(1 \le i \le N)$ ~(1 \le i \le N)~ is waiting at the distance of $A_i$ ~A_i~ meters from the northernmost point of the lake, in the clockwise direction. The values of $A_i$ ~A_i~ $(1 \le i \le N)$ ~(1 \le i \le N)~ are distinct. The apple tree $j$ ~j~ $(1 \le j \le M)$ ~(1 \le j \le M)~ is grown up at the distance of $B_j$ ~B_j~ meter from the northernmost point of the lake, in the clockwise direction. The values of $B_j$ ~B_j~ $(1 \le j \le M)$ ~(1 \le j \le M)~ are distinct. Moreover, there is no apple tree at the initial position of any employee.

Due to a special breed improvement of the apple trees in IOI Farm, every apple tree can have at most one apple at the same time. Moreover, if an apple is harvested from the apple tree, it will have a new apple exactly after $C$ ~C~ seconds. At time $0$ ~0~, every apple tree has an apple, and every employee starts walking around the lake in the clockwise direction. The speed of every employee is $1$ ~1~ meter per second. If an employee arrives at an apple tree with an apple, then the employee will always harvest it (If an apple tree has a new apple at the same time when an employee arrives there, then the employee will harvest it too). We ignore the time it takes for an employee to harvest an apple.

President K is a stockholder of IOI Farm. Since you are a manager of IOI Farm, President K asked you to report on the efficiency of the employees. More precisely, President K wants to know the following $Q$ ~Q~ values.

For each $k$ ~k~ $(1 \le k \le Q)$ ~(1 \le k \le Q)~, the number of apples harvested by the employee $V_k$ ~V_k~ until time $T_k$ ~T_k~ (including an apple harvested exactly at time $T_k$ ~T_k~ if it exists).

Write a program which, given the number of employees, the number of apple trees, the perimeter of the lake, the time it takes for an apple tree to have a new apple, the positions of the employees and the apple trees, and information on $Q$ ~Q~ queries, calculates the number of harvested apples for each query.

Input Specification

$N\ M\ L\ C$ ~N\ M\ L\ C~

$A_1 \dots A_N$ ~A_1 \dots A_N~

$B_1 \dots B_M$ ~B_1 \dots B_M~

$Q$ ~Q~

$V_1\ T_1$ ~V_1\ T_1~

$\dots$ ~\dots~

$V_Q\ T_Q$ ~V_Q\ T_Q~

Output Specification

Write $Q$ ~Q~ lines to the standard output. In the $k$ ~k~-th line $(1 \le k \le Q)$ ~(1 \le k \le Q)~, output the answer to the $k$ ~k~-th query.

Constraints

$1 \le N \le 2 \times 10^5$ ~1 \le N \le 2 \times 10^5~.

$1 \le M \le 2 \times 10^5$ ~1 \le M \le 2 \times 10^5~.

$N+M \le L \le 10^9$ ~N+M \le L \le 10^9~.

$1 \le C \le 10^9$ ~1 \le C \le 10^9~.

$0 \le A_i < L$ ~0 \le A_i < L~ $(1 \le i \le N)$ ~(1 \le i \le N)~.

$A_i < A_{i+1}$ ~A_i < A_{i+1}~ $(1 \le i \le N-1)$ ~(1 \le i \le N-1)~.

$0 \le B_j < L$ ~0 \le B_j < L~ $(1 \le j \le M)$ ~(1 \le j \le M)~.

$B_j < B_{j+1}$ ~B_j < B_{j+1}~ $(1 \le j \le M-1)$ ~(1 \le j \le M-1)~.

$A_i \ne B_j$ ~A_i \ne B_j~ $(1 \le i \le N, 1 \le j \le M)$ ~(1 \le i \le N, 1 \le j \le M)~.

$1 \le Q \le 2 \times 10^5$ ~1 \le Q \le 2 \times 10^5~.

$1 \le V_k \le N$ ~1 \le V_k \le N~ $(1 \le k \le Q)$ ~(1 \le k \le Q)~.

$1 \le T_k \le 10^{18}$ ~1 \le T_k \le 10^{18}~ $(1 \le k \le Q)$ ~(1 \le k \le Q)~.

Subtasks

(5 points) $N \le 3 \times 10^3$ ~N \le 3 \times 10^3~, $M \le 3 \times 10^3$ ~M \le 3 \times 10^3~, $Q \le 3 \times 10^3$ ~Q \le 3 \times 10^3~.
(20 points) $T_k \ge 10^{15}$ ~T_k \ge 10^{15}~ $(1 \le k \le Q)$ ~(1 \le k \le Q)~.
(75 points) No additional constraints.

Sample Input 1

Sample Output 1

2
1
1

Explanation for Sample 1

At time $1$ ~1~, the employee $2$ ~2~ harvests an apple from the apple tree $2$ ~2~, and the employee $3$ ~3~ harvests an apple from the apple tree $1$ ~1~.
At time $3$ ~3~, the employee $2$ ~2~ arrives at the apple tree $1$ ~1~. Since it has no apple at that time, the employee does not harvest an apple.
At time $4$ ~4~, the employee $1$ ~1~ harvests an apple from the apple tree $2$ ~2~.
At time $6$ ~6~, the employee $1$ ~1~ harvests an apple from the apple tree $1$ ~1~. The employee $3$ ~3~ arrives at the apple tree $2$ ~2~, but does not harvest an apple since the apple tree has no apple at that time.
At time $8$ ~8~, the employee $2$ ~2~ harvests an apple from the apple tree $2$ ~2~. The employee $3$ ~3~ arrives at the apple tree $1$ ~1~, but does not harvest an apple since the apple tree has no apple at that time.

As the number of apples harvested by the employee $1$ ~1~ until time $7$ ~7~ (including an apple harvested at time $7$ ~7~) is $2$ ~2~, output $2$ ~2~ in the first line.

Sample Input 2

5 3 20 6
0 4 8 12 16
2 11 14
9
4 1932
2 93787
1 89
5 98124798
1 2684
1 137598
3 2
3 8375
4 237

Sample Output 2

Sample Input 3

8 15 217 33608
0 12 71 96 111 128 152 206
4 34 42 67 76 81 85 104 110 117 122 148 166 170 212
14
2 223544052420046341
3 86357593875941375
4 892813012303440034
1 517156961659770735
7 415536186438473633
6 322175014520330760
7 557706040951533058
6 640041274241532527
5 286263974600593111
8 349405886653104871
1 987277313830536091
5 989137777159975413
2 50689028127994215
7 445686748471896881

Sample Output 3

33230868503053
3
5
1
123542793648997
8
165811220737767
8
7
1
1
7
7535161012043
132506837660717

Comments

There are no comments at the moment.