help-out-the-indian-army

Protection of the Indian border and safe transport of items from one point to another along the border are the paramount jobs for the Indian army. However they need some information about the protection status along the length of the border. The border can be viewed as the real x-axis. Along the axis, Indian army 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 military assistance of all kinds. The size of the fleet is based on the location of the checkpoint and how active the region is for terrorist activities.

Given the number of armed men assigned at the i^th checkpoint, as pi, this information is available for all checkpoints. 
With the skills of the armed men, it is known that if for the i^th 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 military items from position S to the end position E on the x-axis.
Input:
First line of the input contains 3 integers N, S and E. N is the number of checkpoints that the Indian Army has on the border.
Then N lines follow. i^th line contains 2 integers, xi and pi.

Output:
Print the total distance of the x-axisfrom S to E, that is not protected by the armed forces.

Constraints:
1 ≤ N ≤ 10^5
1 ≤ xi, pi ≤ 10^18
xi + pi ≤ 10^18
1 ≤ S ≤ E ≤ 10^18

SAMPLE INPUT
5 229 8419
1795 95
4873 720
3149 81
6101 2325
3674 629

SAMPLE OUTPUT
2626

Source: hackerearth | Difficulty: MEDIUM
Tags: Sorting


Solutions:
n,beg,end =list(map(int, input().split()))
s = 0
e = 0
if beg < end:
	s = beg
	e= end
else:
	s = end
	e = beg
arr = {}
arr1 = {}
for _ in range(n):
	x,p = list(map(int, input().split()))
	arr[x] = p
dic = {}
for k in arr:
	mx = k + arr[k]
	mn = k - arr[k]
	dic[mn] = mx
arr1 = sorted(dic.items())
i = 0
cur = s
res = 0
#print arr1
while cur < e and i < n:
	if cur <= arr1[i][0]:
		if e > arr1[i][0]:
			res += (arr1[i][0] - cur)
			cur = arr1[i][1]
		else:
			#print cur
			res +=(e-cur)
			cur = e
			
	else:
		if cur < arr1[i][1]:
			cur = arr1[i][1]
	i +=1

if cur < e and res:
	res +=(e-arr1[n-1][1])
if res == 0:
	res = e-s
print(res)


n, s, e = [int(i) for i in input().split()]

res = 0
a = []
for i in range(n):
	x, p = [int(j) for j in input().split()]
	a.append([min(max(1, x-p, s), e), max(min(x+p, e), s)])

a.sort(key = lambda x:x[0])

tlen = e-s+1
clen = 0
i = 1
curr = a[0][1]
clen += (max(0, a[0][0]-s))
while i < n:
	if curr > a[i][0]:
		curr = max(curr, a[i][1])
		i += 1
	else:
		clen += (a[i][0] - curr)
		curr = a[i][1]
		i += 1
clen += (max(0, e - curr))
print(clen)


N,S,E = list(map(int, input().split()))
data = []
for i in range(N):
	x,p = list(map(int, input().split()))
	data.append([x-p, x+p])
	
#print 'S is:{0} and E is:{1}'.format(S,E)
#print data
data.sort()
diff = 0
for i in range(len(data)):
	temp_arr = data[i]
	temp_start = temp_arr[0]
	temp_end = temp_arr[1]
	#print 's is: {0} and e is: {1}'.format(temp_start, temp_end)
	if temp_start >= E:
		break
	if temp_start > S:
		diff += temp_start - S
		S = temp_end
		#print 'Diff is: {0}'.format(diff)
	elif S >=temp_start and S <= temp_end:
		S = temp_end
	else:
		pass
	if temp_end > E:
		break

if S < E:
	diff += (E - S)

print('{0}'.format(diff))