missing-soldiers-december-easy-easy

An infinite army of ants is marching on an infinite 2-D plane. Since ants are disciplined, here's how they march: each ant chooses exactly one x coordinate and moves along it in positive y direction, starting from (x, 0). There exists exactly one ant for each x coordinate on that plane and hence there are infinite ants!

There are N horizontal barriers lying on this plane. The i^th barrier is defined by (xi, yi) and di, which means that the barrier is blocking all ants which want to pass through points lying on line segment connecting (xi, yi) and (xi + di, yi). Once an ant encounters a barrier, it stops moving.

Given all the barriers, your task is to find the total number of ants, that will be ever blocked at some point in their march.

INPUT

The first line contains an integer N which denotes the number of barriers. Next N lines follow, each contains 3 space separated integers,  "xi yi di" as explained in problem statement above.

Note: The barriers in the input may overlap.

OUTPUT

Output a single integer, the number of ants that will be ever blocked at some point in their march.

CONSTRAINTS

1 ≤ N ≤ 10^5
1 ≤ xi, yi, di ≤ 10^9

SAMPLE INPUT
2
1 1 4
7 3 5

SAMPLE OUTPUT
11

Explanation

Here 5 ants will be blocked on points (1,1) , (2, 1) , (3, 1), (4, 1) and (5, 1).

6 ants will be blocked on (7, 3), (8, 3), (9, 3), (10, 3), (11, 3), (12, 3).

In total, 11 ants are blocked in their journey.

Difficulty: EASY

Starter code:

Solutions:
l = []
for _ in range(int(input())):
	x,y,d = list(map(int,input().split()))
	l.append((x,d))
l.sort(key=lambda x: x[0])
start,d = l.pop(0)
s = d+1
last = start + d
for start,d in l:
	if start > last:
		s += d+1
		last = start + d
	elif start <= last and start+d > last:
		s += start + d - last
		last = start + d
print(s)


N = int(input())
l = [(0,0,0)] * N

for i in range(N):
	l[i] = list(map(int, input().split(' ')))

l = sorted(l, key=lambda a: a[0])

s = 0
end = None
for i in range(N):
	(x, _, d) = l[i]
	if end is None:
		start = x
	else:
		start = max(x, end + 1)
	end = max(x + d, end)
	s += max(0, end - start + 1)
print(s)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
n=int(input())
bar=[]
for i in range(n):
	temp=list(map(int,input().split()))
	bar.append(temp[:])
import operator
bar.sort(key=operator.itemgetter(0))
aunt=0

i=1
s=bar[0][0]
e=s+bar[0][2]
while i<len(bar):	
	if e>bar[i][0]:
		if bar[i][0]+bar[i][2]>e:
			e=bar[i][0]+bar[i][2]
	else:
		aunt+=e-s+1
		s=bar[i][0]
		e=s+bar[i][2]
	i+=1	
aunt+=e-s+1	
print(aunt)	


def solve(n,l):
	l.sort()
	c = 0
	o = 0
	for x,g in l:
		if g == 0:
			o += 1
			if o == 1: p = x
		else:
			o -= 1
			if o == 0: c += (x - p) + 1
	return c

n = int(input())
l = []
for i in range(n):
	x,y,d = list(map(int,input().strip().split()))
	l.append((x,0))
	l.append((x+d,1))
print(solve(n,l))


from sys import stdin

def main():
	nextint = iter(map(int, stdin.read().split())).__next__
	arr = []
	for _ in range(nextint()):
		x, y, d = nextint(), nextint(), nextint()
		arr.append((x, x + d))
	blocked, end = 0, 0
	for x, y in sorted(arr):
		if x > end:
			blocked += y - x + 1
			end = y
		elif y > end:
			blocked += y - end
			end = y
	print(blocked)

main()



# Read input from stdin and provide input before running code

N = int(input());
bigArr = [];
while (N > 0) :
	xyd = list(map(int, input().strip().split(' ')));
	bigArr.append(xyd);
	N -= 1;
bigArr = sorted(bigArr, key = lambda x : x[0]);
res = 0;
fncp = 1;
for i in bigArr :
	fncp = max(fncp, i[0]);
	if (fncp <= i[0] + i[2]):
		res += (i[0] + i[2] - fncp + 1);
		fncp = i[0] + i[2] + 1;
print(res);


n = int(input())
l = []
for _ in range(n):
	x,y,d = list(map(int,input().split()))
	l.append((x,d))
l.sort(key=lambda x: x[0])
start,d = l.pop(0)
sum = d+1
last = start + d
for start,d in l:
	if start > last:
		sum += d+1
		last = start + d
	elif start <= last and start+d > last:
		sum += start + d - last
		last = start + d
print(sum)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
lines = int(input())
line_set = []

for i in range(lines):
	inp = input()
	line_set.append(list(int(i) for i in iter(inp.split())))

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

result = 0
sp = 1
for x, _, d in line_set:
	sp = max(sp, x)
	if x+d >= sp:
		result += x+d-sp+1
		sp = x+d+1

print(result)