UCC Coding Competition '21 P3 - Long Pizza

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types

You are in charge of adding cheese topping to a pizza prepared for a special customer. This pizza is a very long rectangular strip. It is divided into N slices, numbered 1 to N from left to right. To add cheese topping to the pizza, you have a special machine that can add 1 unit of cheese on each slice in a consecutive group of slices (for example, you can add 1 unit of cheese on each slice between slice 2 and 4 inclusive, adding a total of 3 units of cheese). Each slice can carry an unlimited amount of cheese.

You plan to run the machine R times, each time adding 1 unit of cheese to each slice in a given range.

The customer is on a diet. When he eats the section of pizza from slice x to slice y, inclusive, he would like to know how many units of cheese he is consuming.

NOTE FOR PYTHON USERS: If your program receives TLE (time limit exceeded), you should try submitting using the PyPy interpreter: when you are submitting your code, try using "PyPy 3" or "PyPy 2" as the language, instead of "Python 3" or "Python 2".

Input Specification

The first line will contain the integer N, the length of your long pizza.

The second line will consist of two space-separated integers x and y, indicating that the customer is planning to eat every slice between slice x and slice y inclusive.

The third line will contain the integer R, the number of times you plan to run the topping machine.

The following R lines will each describe one planned run of the topping machine using 2 space-separated integers, l and r (l \le r), indicating that the machine will add 1 unit of cheese onto each slice between slices l and r, inclusive.

Output Specification

Please output the total number of units of cheese on all of the slices the customer is planning to eat.

Constraints and Partial Marks

For 4 of the 10 available marks, R \le 1000 and N \le 10^5.

For the remaining 6 marks, R \le 4000 and N \le 10^7.

Sample Input

3 5
2 6
4 5
3 3

Sample Output


Explanation of Sample Output

After running the machine three times, the amount of cheese on each slice of pizza is as follows:

Slice #:  1  2  3  4  5  6  7  8  9  10
Cheese:   0  1  2  2  2  1  0  0  0  0

Therefore, slices 3-5 have a total of 6 units of cheese.


There are no comments at the moment.