Lampice
레이팅 미적용의견: 0
Christmas is coming! Teo has already decided to decorate his terrace.
Teo has a big rectangul\(ar-sh\)aped terrace. It is \(n\) meters long and \(m\) meters wide.
Teo has decided to decorate his terrace in a very strange way. Instead of hanging
Christmas lights on the edges of his terrace, he will put them on the floor!
Teo has 2\(k\) lamps, two per each of \(k\) colours. He will put each in some position
(\(x@@RISE_MATH_BLOCK_0@@i\) represents the distance from the left side of the terrace and \(y\)\(i\)
from the bottom side.
Proud of how he decorated the terrace, he decided to take the rest of his day off. But soon he got bored,
so he returned to the terrace. He started counting nice rectangles on the terrace. A rectangle is nice if for
each colour both lamps are either inside or outside of the rectangle. If a lamp is located on the rectangle
edge, it is considered to be inside of it.
The left rectangle \(is\) not nice. One blue lamp \(is\) inside the rectangle, and one \(is\) outside.
The right rectangle \(is\) nice. Red and blue lamps are inside. Yellow lamps are outside.
Teo has realized that counting nice rectangles is not an easy job. He is interested in how many nice
rectangles are there, whose corners have integer distances from the bottom and left sides of the terrace.
All rectangles we consider are parallel with terrace sides. This is where you step in! Count the number
of nice rectangles.
Subtask 1 (26 points): \(x@@RISE_MATH_BLOCK_0@@1 = 0\) for each lamp colour
Subtask 2 (12 points): n, \(m \le 10\), \(k \le 1\,000\)
Subtask 3 (35 points): \(m \le 150\)
Subtask 4 (37 points): No additional constraints.
The first line contains three integers n, m, k (\(1 \le n \le 150\), \(1 \le m \le 1\,000\), \(0 \le k \le 200\,000\)), the length
and the width of the terrace, and the number of lamp colours.
The next \(k\) lines contain four numbers \(x_{1}\), y_{1}, x_{2}, y_{2} (\(0 \le x_{1}\), \(x_{2} \le n\), \(0 \le y_{1}\), \(y_{2} \le m\)), positions of the first
and the second lamp of the \(i-th\) colour.
In a single line output the number of nice rectangles.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 26점 | \(x@@RISE_MATH_BLOCK_0@@1 = 0\) for each lamp colour |
2 | 12점 | n, \(m \le 10\), \(k \le 1\,000\) |
3 | 35점 | \(m \le 150\) |
4 | 37점 | No additional constraints. |
2 2 1
0 0 1 233 3 0363 3 5
0 0 0 0
0 0 1 3
0 0 3 1
1 3 3 1
1 3 3 17Clarification of the first example:
The image shows all nice rectangles from the first example.
평가 및 의견
Lampice
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Lampice