NOI '20 P3 - Tears

View as PDF

Points: 30 (partial)
Time limit: 4.0s
Memory limit: 1G

Problem type

Let denote two points on the plane satisfies . There are events denoted by distinct points on the plane. There are epochs denoted by a rectangle where is the bottom-left corner of the rectangle and is the upper-right corner, and it is guaranteed that . We say epoch includes event if and only if .

If two events satisfy , then the two events constitute an occurrence of sadness. For all events in an epoch, the occurrences of sadness are called the tear of the epoch, and the size of the tear of the epoch is measured by the number of occurrences of sadness. We'd like to compute the size of the tears of the epochs.

Input Specification

The first line contains two integers denoting the number of events and the number of epochs. The second line contains integers , and the -th number denotes event has coordinate on the plane. It is guaranteed that is a permutation of . In the following lines, each line contains four integers denoting the rectangle corresponding to the epoch.

Output Specification

There are lines and each line contains an integer. The -th line denotes the size of the tear of epoch .

Sample Input 1

9 9
9 8 7 6 2 4 5 3 1
4 9 3 6
2 9 1 8
3 8 2 4
3 9 2 7
2 8 1 6
1 9 1 9
1 3 5 7
2 3 3 3
6 6 6 6

Sample Output 1

1
4
2
4
4
4
0
0
0

For all test cases, , , .

1~3None.
4
5
6
7For every epoch , we have and .
8
9
10
11For any two rectangles representing different epochs, either one is contained in another (the boundaries may overlap) or they are disjoint.
12
13
14None.
15
16
17
18
19
20~22There exists at most 50 pairs of events () that do not satisfy .
23~25None.