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

Restore Atlantis II

Time Limit: 15000/15000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 28    Accepted Submission(s): 8


Problem Description
There are $n$ ancient Greek maps describing the fabled islands Atlantis. The maps are labeled by $1,2,\dots,n$. The $i$-th map shows the rectangle area $R_i$ is a part of Atlantis. The sides of all rectangles are parallel to the axes. There may be multiple islands, and the rectangles may overlap.

Unfortunately, some maps are even unreliable so they will not be considered. You will be given $q$ queries. In the $i$-th query, you will be given two integers $s_i$ and $t_i$ ($1\leq s_i\leq t_i\leq n$). Please write a program to figure out the total area of Atlantis when only maps labeled by $k$ ($s_i\leq k\leq t_i$) are reliable.
 

Input
The first line contains a single integer $T$ ($1 \leq T \leq 3$), the number of test cases. For each test case:

The first line of the input contains two integers $n$ and $q$ ($1 \leq n,q \leq 100\,000$), denoting the number of maps and the number of queries.

In the next $n$ lines, the $i$-th line contains four integers $xa_i$, $ya_i$, $xb_i$ and $yb_i$ ($0\le xa_i<xb_i\leq 10^9$, $0\le ya_i<yb_i\leq 10^9$), describing the $i$-th map $R_i$. $(xa_i,ya_i)$ is the southwest corner of $R_i$, and $(xb_i,yb_i)$ is the northeast corner of $R_i$.

In the next $q$ lines, the $i$-th line contains two integers $s_i$ and $t_i$ ($1\leq s_i\leq t_i\leq n$), describing the $i$-th query.

It is guaranteed that all the values of $xa_i$, $ya_i$, $xb_i$, $yb_i$, $s_i$ and $t_i$ are chosen uniformly at random from integers in their corresponding ranges. The randomness condition does not apply to the sample test case, but your solution must pass the sample as well.
 

Output
For each query, print a single line containing an integer, denoting the total area using the information of all reliable maps in this query.
 

Sample Input
1 3 6 10 10 20 20 12 12 22 22 15 15 25 25 1 1 2 2 3 3 1 2 2 3 1 3
 

Sample Output
100 100 100 136 151 187
 

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-03-29 12:59:21, Gzip enabled