F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Problem J. Rectangle Radar Scanner

Time Limit: 20000/15000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 573    Accepted Submission(s): 172


Problem Description
There are $n$ houses on the ground, labeled by $1$ to $n$. The $i$-th house is located at $(i,y_i)$, and there is a spy transmitter with energy $w_i$ inside the $i$-th house.
Little Q has a rectangle radar scanner, which can find all the transmitters within the range $[xl,xr]\times[yl,yr]$. That means a transmitter located at $(x,y)$ can be found if $xl\leq x\leq xr$ and $yl\leq y\leq yr$.
Your task is to achieve the scanner efficiently.
Given $m$ queries $xl_i,xr_i,yl_i,yr_i$, for each query, please find all the transmitters within the range, then report the product of their energy and the maximum/minimum energy among them.
To reduce the large input, we will use the following generator. The numbers $a_0,b_0,c_0,d_0,p,q,r$ and $MOD$ are given initially. The values $a_i,b_i,c_i,d_i,xl_i,xr_i,yl_i,yr_i$ are then produced as follows :
\begin{eqnarray*}
a_i&=&(p\times a_{i-1}+q\times b_{i-1}+r)\bmod MOD\\
b_i&=&(p\times b_{i-1}+q\times a_{i-1}+r)\bmod MOD\\
c_i&=&(p\times c_{i-1}+q\times d_{i-1}+r)\bmod MOD\\
d_i&=&(p\times d_{i-1}+q\times c_{i-1}+r)\bmod MOD\\
xl_i&=&\min(a_i\bmod n,b_i\bmod n)+1\\
xr_i&=&\max(a_i\bmod n,b_i\bmod n)+1\\
yl_i&=&\min(c_i\bmod n,d_i\bmod n)+1\\
yr_i&=&\max(c_i\bmod n,d_i\bmod n)+1
\end{eqnarray*}
 

Input
The first line of the input contains an integer $T(1\leq T\leq3)$, denoting the number of test cases.
In each test case, there is an integer $n(1\leq n\leq 100000)$ in the first line, denoting the number of houses.
In the next $n$ lines, each line contains $2$ integers $y_i,w_i(1\leq y_i\leq n,1\leq w_i\leq 10^9)$, describing a house.
Then in the next line, there are $10$ integers $m,a_0,b_0,c_0,d_0,p,q,r,MOD,k$, describing the queries. It is guaranteed that $1\leq m\leq 10^6$ and $5\leq a_0,b_0,c_0,d_0,p,q,r,MOD,k\leq 10^9$.
 

Output
Since the output file may be very large, let's denote $prod_i$ as the product of of the $i$-th query, $max_i$ as the maximum energy of the $i$-th query, and denote $min_i$ as the minimum energy of the $i$-th query. Note that when there are no avaliable transmitters, then $prod_i=max_i=min_i=0$.
For each test case, you need to print a single line containing an integer $answer$, where :
\begin{eqnarray*}
answer&=&\sum_{i=1}^{m} ((prod_i\bmod k)\oplus max_i\oplus min_i)
\end{eqnarray*}
Note that ``$\oplus$'' denotes binary XOR operation.
 

Sample Input
1 5 2 6 1 8 5 2 4 9 2 4 3 5 6 7 8 9 8 7 998244353 10007
 

Sample Output
68
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-02 10:31:32, Gzip enabled