日度归档：18 2 月, 2017

数据结构 邓俊辉 PA#1 灯塔(LightHouse) 题解

发表评论

灯塔(LightHouse)

Description

As shown in the following figure, If another lighthouse is in gray area, they can beacon each other.

For example, in following figure, (B, R) is a pair of lighthouse which can beacon each other, while (B, G), (R, G) are NOT.

Input

1st line: N

2nd ~ (N + 1)th line: each line is X Y, means a lighthouse is on the point (X, Y).

Output

How many pairs of lighthourses can beacon each other

( For every lighthouses, X coordinates won’t be the same , Y coordinates won’t be the same )

Example

Input

3
2 2
4 3
5 1

Output

1

Restrictions

For 90% test cases: 1 <= n <= 3 * 105

For 95% test cases: 1 <= n <= 106

For all test cases: 1 <= n <= 4 * 106

For every lighthouses, X coordinates won’t be the same , Y coordinates won’t be the same.

1 <= x, y <= 10^8

Time: 2 sec

Memory: 256 MB

Hints

The range of int is usually [-231, 231 – 1], it may be too small.

描述

海上有许多灯塔，为过路船只照明。

（图一）

如图一所示，每个灯塔都配有一盏探照灯，照亮其东北、西南两个对顶的直角区域。探照灯的功率之大，足以覆盖任何距离。灯塔本身是如此之小，可以假定它们不会彼此遮挡。

（图二）

若灯塔A、B均在对方的照亮范围内，则称它们能够照亮彼此。比如在图二的实例中，蓝、红灯塔可照亮彼此，蓝、绿灯塔则不是，红、绿灯塔也不是。

现在，对于任何一组给定的灯塔，请计算出其中有多少对灯塔能够照亮彼此。

输入

共n+1行。

第1行为1个整数n，表示灯塔的总数。

第2到n+1行每行包含2个整数x, y，分别表示各灯塔的横、纵坐标。

输出

1个整数，表示可照亮彼此的灯塔对的数量。

样例

见英文题面

限制

对于90%的测例：1 ≤ n ≤ 3×105

对于95%的测例：1 ≤ n ≤ 106

全部测例：1 ≤ n ≤ 4×106

灯塔的坐标x, y是整数，且不同灯塔的x, y坐标均互异

1 ≤ x, y ≤ 10^8

时间：2 sec

内存：256 MB

提示

注意机器中整型变量的范围，C/C++中的int类型通常被编译成32位整数，其范围为[-231, 231 – 1]，不一定足够容纳本题的输出。

继续阅读 →

数据结构 邓俊辉 PA#1 范围查询(Range) 题解

发表评论

范围查询(Range)
Description
Let S be a set of n integral points on the x-axis. For each given interval [a, b], you are asked to count the points lying inside.

Input
The first line contains two integers: n (size of S) and m (the number of queries).

The second line enumerates all the n points in S.

Each of the following m lines consists of two integers a and b and defines an query interval [a, b].

Output
The number of points in S lying inside each of the m query intervals.

Example
Input

5 2
1 3 7 9 11
4 6
7 12
Output

0
3
Restrictions
0 <= n, m <= 5 * 10^5 For each query interval [a, b], it is guaranteed that a <= b. Points in S are distinct from each other. Coordinates of each point as well as the query interval boundaries a and b are non-negative integers not greater than 10^7. Time: 2 sec Memory: 256 MB 描述 数轴上有n个点，对于任一闭区间 [a, b]，试计算落在其内的点数。 输入 第一行包括两个整数：点的总数n，查询的次数m。 第二行包含n个数，为各个点的坐标。 以下m行，各包含两个整数：查询区间的左、右边界a和b。 输出 对每次查询，输出落在闭区间[a, b]内点的个数。 样例 见英文题面 限制 0 ≤ n, m ≤ 5×105 对于每次查询的区间[a, b]，都有a ≤ b 各点的坐标互异 各点的坐标、查询区间的边界a、b，均为不超过10^7的非负整数 时间：2 sec 内存：256 MB 继续阅读 →