Yet Another Contest 5 P5 - No More Concerts

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.0s
Java 4.0s
Python 4.0s
Memory limit: 512M

Problem types

Mike is sick of listening to concerts during lunchtime at his school! Unfortunately for him, a single concert will be hosted on the school field on each of the next N days.

The school field can be represented as a rectangle with the bottom-left corner (0, 0) and upper-right corner (W, H) on a 2-D Cartesian plane, and the location of each concert can be represented by a single point within the rectangle. There is also a concession area, whose initial location can be represented as a rectangle with the bottom-left corner (0, 0) and upper-right corner (W, 1).

On the first day, the concert will be hosted at (x_1, y_1). At the end of the i-th day, the concert will be moved by a_i units to the right and b_i units upwards. To maximize attraction, the concession stand will adjust accordingly and move its upper-right corner b_i units upwards. Note that the bottom-left corner of the concession area always remains at (0, 0).

Since Mike does not like listening to repetitive music and would much rather buy snacks from the concession, he wants to choose a rectangular region within the school field to eat his lunch such that over the N days, no point within the rectangular region is ever closer to the concert than the concession area, in terms of Euclidean distance. The rectangular region must be axis-aligned, have a positive area, and the bottom-left corner and upper-right corner of the rectangle must have integral coordinates.

The distance between a point and the concession area is defined as the shortest Euclidean distance between the point and any point inside the rectangular region, including on its boundary. Of course, if a point resides within the concession area, its distance to the concession area is 0.

Can you help Mike find the number of possible rectangle regions that he can eat his lunch at over the next N days? Since this value may be large, output it modulo 998\,244\,353.


1 \le N, W \le 10^6

2 \le H \le 10^9

0 \le x_1 \le W

2 \le y_1 \le H

|a_i| \le W

|b_i| \le H

It is guaranteed that each concert will remain within the school field, possibly on its boundary.

It is guaranteed that the y-coordinate of the concession area will always be positive.

Subtask 1 [15%]

W = 1

Subtask 2 [15%]

a_i = 0

Subtask 3 [35%]

1 \le N \le 20

Subtask 4 [35%]

No additional constraints.

Input Specification

The first line contains three integers, N, W and H.

The second line contains two integers, x_1 and y_1.

The next N-1 lines contain two integers, a_i and b_i, representing the horizontal shift and vertical shift of the concert at the end of the i-th day.

Output Specification

On a single line, print the number of possible rectangular regions that Mike can choose modulo 998\,244\,353.

Sample Input 1

2 5 4
2 2
1 1

Sample Output 1


Explanation for Sample Output 1

One possible rectangular region that Mike can select is highlighted yellow in the diagram below. It can be shown that no point within this rectangle is closer to the concert than the concession area on either day.

Sample Input 2

1 2 2
1 2

Sample Output 2


Explanation for Sample Output 2

The 3 possible rectangular regions that Mike can select are shown below.

Sample Input 3

3 1000000 1000000000
101010 101010101
101010 101010101
101010 101010101

Sample Output 3


Explanation for Sample Output 3

Be sure to print the result modulo 998\,244\,353.

Sample Input 4

6 49 20
9 10
21 0
-30 10
49 -5
0 0
-9 -4

Sample Output 4



There are no comments at the moment.