APIO '19 P1 - Strange Device - Olympiads Online Judge

APIO '19 P1 - Strange Device

View as PDF

Submit solution

All submissions

Best submissions

Points: 20

Time limit: 1.8s

Memory limit: 512M

Problem type

Archaeologists have found a strange device that was probably created by some ancient civilization. The device has a screen that displays two integers: $x$ ~x~ and $y$ ~y~.

After exploring the device the scientists have made a conclusion that the device is kind of a clock. It measures time $t$ ~t~ passed from some moment in the past, but shows it in some weird way, probably used by the creators of the device. If the time passed is an integer $t$ ~t~, the two integers displayed are: $x = ((t + \left\lfloor \frac t B \right\rfloor) \bmod A)$ , and $y = (t \bmod B)$ ~y = (t \bmod B)~. Here $\left\lfloor x \right\rfloor$ ~\left\lfloor x \right\rfloor~ is the floor function — the greatest integer less or equal to $x$ ~x~.

The archaeologists have studied the device and found out that its screen wasn't turned on all the time. Actually it was only working during $n$ ~n~ continuous periods of time, the $i$ ~i~-th of them was from the moment $l_i$ ~l_i~ to the moment $r_i$ ~r_i~, inclusive. Now the scientists would like to calculate how many distinct pairs $(x, y)$ ~(x, y)~ were shown by the device when its screen was on.

Two pairs $(x_1, y_1)$ ~(x_1, y_1)~ and $(x_2, y_2)$ ~(x_2, y_2)~ are distinct if $x_1 \ne x_2$ ~x_1 \ne x_2~ or $y_1 \ne y_2$ ~y_1 \ne y_2~.

Input Specification

The first line contains three integers $n$ ~n~, $A$ ~A~, and $B$ ~B~ ( $1 \le n \le 10^6$ ~1 \le n \le 10^6~; $1 \le A, B \le 10^{18}$ ~1 \le A, B \le 10^{18}~).

Each of the following $n$ ~n~ lines contains two integers $l_i$ ~l_i~ and $r_i$ ~r_i~, the beginning and the end of the $i$ ~i~-th segment $[l_i, r_i]$ ~[l_i, r_i]~ when the device screen was turned on ( $0 \le l_i \le r_i \le 10^{18}$ ~0 \le l_i \le r_i \le 10^{18}~; $r_i < l_{i+1}$ ~r_i < l_{i+1}~).

Output Specification

Output the number of distinct pairs $(x, y)$ ~(x, y)~ that were shown on the device screen when it was turned on.

Scoring

Let $S = \sum_{i=1}^n (r_i - l_i + 1)$ ~S = \sum_{i=1}^n (r_i - l_i + 1)~ and $L = \max_{1 \le i \le n} (r_i - l_i + 1)$ .

Subtask 1 (points: 10)

$S \le 10^6$ ~S \le 10^6~

Subtask 2 (points: 5)

$n = 1$ ~n = 1~

Subtask 3 (points: 5)

$A \cdot B \le 10^6$ ~A \cdot B \le 10^6~

Subtask 4 (points: 5)

$B = 1$ ~B = 1~

Subtask 5 (points: 5)

$B \le 3$ ~B \le 3~

Subtask 6 (points: 20)

$B \le 10^6$ ~B \le 10^6~

Subtask 7 (points: 20)

$L \le B$ ~L \le B~

Subtask 8 (points: 30)

No additional constraint.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

2 16 13
2 5
18 18

Sample Output 3

Explanation

In the first test, the device screen shows the following integers.

$t = 4$ ~t = 4~, $(x, y) = (2, 1)$ ~(x, y) = (2, 1)~

$t = 7$ ~t = 7~, $(x, y) = (0, 1)$ ~(x, y) = (0, 1)~

$t = 8$ ~t = 8~, $(x, y) = (1, 2)$ ~(x, y) = (1, 2)~

$t = 9$ ~t = 9~, $(x, y) = (0, 0)$ ~(x, y) = (0, 0)~

$t = 17$ ~t = 17~, $(x, y) = (1, 2)$ ~(x, y) = (1, 2)~

$t = 18$ ~t = 18~, $(x, y) = (0, 0)$ ~(x, y) = (0, 0)~

So there are four distinct pairs $(0, 0)$ ~(0, 0)~, $(0, 1)$ ~(0, 1)~, $(1, 2)$ ~(1, 2)~, $(2, 1)$ ~(2, 1)~.

Comments

4

Aaeria commented on Oct. 1, 2019, 6:10 p.m.

$AB\le10^{19}$ ~AB\le10^{19}~

0

Plasmatic commented on May 15, 2020, 2:15 a.m. ← edit 2 →

It's actually even smaller: $A \times B$ ~A \times B~ fits inside a long long. ( $10^{19} \ge 2^{63}$ ~10^{19} \ge 2^{63}~)