A. Polo the Penguin and Segments
Time Limit : 4000/2000ms (Java/Other) Memory Limit : 524288/262144K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
Problem Description
Little penguin Polo adores integer segments, that is, pairs of integers [l;r] (l¡Ür).
He has a set that consists of n integer segments: [l1;r1],[l2;r2],...,[ln;rn]. We know that no two segments of this set intersect. In one move Polo can either widen any segment of the set 1 unit to the left or 1 unit to the right, that is transform [l;r] to either segment [l-1;r], or to segment [l;r+1].
The value of a set of segments that consists of n segments [l1;r1],[l2;r2],...,[ln;rn] is the number of integers x, such that there is integer j, for which the following inequality holds, lj¡Üx¡Ürj.
Find the minimum number of moves needed to make the value of the set of Polo's segments divisible by k.
Input
<p>The first line contains two integers <span class="tex-span"><i>n</i></span> and <span class="tex-span"><i>k</i></span> (<span class="tex-span">1¡Ü<i>n</i>,<i>k</i>¡Ü10<sup class="upper-index">5</sup></span>). Each of the following <span class="tex-span"><i>n</i></span> lines contain a segment as a pair of integers <span class="tex-span"><i>l</i><sub class="lower-index"><i>i</i></sub></span> and <span class="tex-span"><i>r</i><sub class="lower-index"><i>i</i></sub></span> (<span class="tex-span">-10<sup class="upper-index">5</sup>¡Ü<i>l</i><sub class="lower-index"><i>i</i></sub>¡Ü<i>r</i><sub class="lower-index"><i>i</i></sub>¡Ü10<sup class="upper-index">5</sup></span>), separated by a space.</p><p>It is guaranteed that no two segments intersect. In other words, for any two integers <span class="tex-span"><i>i</i>,<i>j</i></span> <span class="tex-span">(1¡Ü<i>i</i><<i>j</i>¡Ü<i>n</i>)</span> the following inequality holds, <span class="tex-span"><i>min</i>(<i>r</i><sub class="lower-index"><i>i</i></sub>,<i>r</i><sub class="lower-index"><i>j</i></sub>)<<i>max</i>(<i>l</i><sub class="lower-index"><i>i</i></sub>,<i>l</i><sub class="lower-index"><i>j</i></sub>)</span>.</p>
Output
<p>In a single line print a single integer the answer to the problem.</p>
Sample Input
2 3 1 2 3 4 3 7 1 2 3 3 4 7
Sample Output
2 0
Source
Codeforces