All submissions for this problem are available.
Protection of the Delhi Girls from R**** became tough. Delhi govt decided to increase no. of checkpoints. However they need some information about the protection status and the distance between checkpoints. The protected length can be viewed as the real x-axis. Along the axis, Delhi police has N checkpoints for lookout.
We know that each checkpoint is located at an integer location xi. Each checkpoint must have a fleet of armed men which are responsible for guarding the neighboring areas of the checkpoint and provide assistance of all kinds. The size of the fleet is based on the location of the checkpoint and how active the region is for criminal activities.
Given the number of armed men assigned at the ith checkpoint, as pi, this information is available for all checkpoints.
With the skills of the armed men, it is known that if for the ith checkpoint, the length on the x axis that they can defend is a closed interval [xi-pi, xi+pi].
Now, your task is to transport some guns from position S to the end position E on the x-axis.
First line of the input contains 3 integers N, S and E. N is the number of checkpoints that the delhi police has on the border.
Then N lines follow. ith line contains 2 integers, xi and pi.
Print the total distance of the x-axis from S to E, that is not protected by the armed forces.
1 ≤ N ≤ 105
1 ≤ xi, pi ≤ 1018
xi + pi ≤ 1018
1 ≤ S ≤ E ≤ 1018
5 229 8419 1795 95 4873 720 3149 81 6101 2325 3674 629
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions