TLE '17 Contest 6 P4 - Willson and Travelling

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 5.0s
Python 18.0s
Memory limit: 512M
Python 640M
Author:

Problem type

Willson flying around a city while making his presence known.

Willson the Canada Goose is like any other Canada Goose - he likes to fly around and practice honking.

Today, he will be flying around a city containing N buildings. Each building is a rectangle with a side parallel to the x axis. The lower left corner of the i^{th} building is at (p_i,q_i), and the upper right corner is at (r_i,s_i). A building can overlap with another building. It is possible for a building to be completely contained within another building. Also, it is possible that two different buildings represent the same rectangle.

However, corners are dangerous for Willson to fly into - much more dangerous than walls. A corner is an integer coordinate where exactly 1 of the 4 adjacent squares is contained within a building. The other 3 adjacent squares are not contained within a building.

Could you tell Willson the number of corners that he needs to look out for?

Constraints

p_i<r_i

q_i<s_i

SubtaskPointsNCoordinate limits
130N = 2All coordinates satisfy 1 \le c \le 2\,000.
2201 \le N \le 30\,000All coordinates satisfy 1 \le c \le 2\,000.
3301 \le N \le 30\,000All coordinates satisfy 1 \le c \le 60\,000.
4201 \le N \le 200\,000All coordinates satisfy 1 \le c \le 500\,000.

Note: Python users are recommended to submit with PyPy. Also, Python users are recommended to optimize their memory usage.

Input Specification

The first line of input will contain a single integer, N.

N lines of input follow. The i^{th} line will contain four integers p_i q_i r_i s_i. The lower left corner of the i^{th} building is at (p_i,q_i), and the upper right corner is at (r_i,s_i). Also, it is guaranteed that p_i<r_i and q_i<s_i.

Output Specification

Output the number of corners that are formed by the buildings.

Sample Input

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

Sample Output

13

Explanation for Sample Output

In the following diagram, the buildings are shown in red and the corners are shown in the black circles.


Comments

There are no comments at the moment.