A cricket match is going to be held. The field is represented by a 1D plane. A cricketer, Mr. X has $N$ favorite shots. Each shot has a particular range.
The range of the  $i^{\mbox{th}}$ shot is from $\mbox{A}_{i}$ to $\mbox{B}_{i}$. That means his favorite shot can be anywhere in this range. Each player on the opposite team 
can field only in a particular range. Player $\boldsymbol{i}$ can field from $\mbox{C}_{i}$ to $\mbox{D}_{i}$. You are given the $N$ favorite shots of Mr. X and the range of $\mbox{M}$ players.

$\mbox{S}_i$ represents the strength of each player i.e. the number of shots player $\boldsymbol{i}$ can stop. 

Your task is to find:

$\left(\textstyle\sum_{i=1}^{m}S i\right)$.

Game Rules: A player can stop the $i^{\mbox{th}}$ shot if the range overlaps with the player's fielding range.

For more clarity about overlapping, study the following figure:  

Input Format

The first line consists of two space separated integers, $N$ and $\mbox{M}$.

Each of the next $N$ lines contains two space separated integers. The $i^{\mbox{th}}$ line contains $A_i$ and $B_i$.

Each of the next $\mbox{M}$ lines contains two integers. The $i^{\mbox{th}}$ line contains integers $C_i$ and $D_i$.

Output Format

You need to print the sum of the strengths of all the players: $\left(\textstyle\sum_{i=1}^{m}S i\right)$.

Constraints:

$1\leq N,M\leq10^5$ 

 $1\leq A_i,B_i,C_i,D_i\leq10^8$

Sample Input
4 4                
1 2 
2 3
4 5
6 7
1 5
2 3
4 7
5 7   

Sample Output
9

Explanation

Player 1 can stop the 1st, 2nd and 3rd shot so the strength is $3$.

  Player 2 can stop the 1st and 2nd shot so the strength is $2$.

  Player 3 can stop the 3rd and 4th shot so the strength is $2$.

  Player 4 can stop the 3rd and 4th shot so the strength is $2$.

The sum of the strengths of all the players is $3+2+2+2=9$.

Source: hackerrank | Difficulty: MEDIUM
Tags: Data structures


Solutions:
import bisect

class IntervalNode:

	def __init__(self, a, b):
		self.midpoint = (a + b) / 2
		self.left = self.right = None
		self.center_left = [a]
		self.center_right = [b]

	def putInterval(self, a, b):
		bisect.insort(self.center_left, a)
		bisect.insort(self.center_right, b)

	def getCrossCount(self, a, b):
		result = 0
		if a <= self.midpoint <= b:
			return len(self.center_left)
		if b < self.midpoint:
			return bisect.bisect_right(self.center_left, b)
		else:
			return len(self.center_right) - bisect.bisect_left(self.center_right, a)

class IntervalTree:

	def __init__(self):
		self.root = None

	def put(self, a, b):
		self.root = self.put_(self.root, a, b)

	def put_(self, node, a, b):
		if node is None:
			return IntervalNode(a, b)
		if b < node.midpoint:
			node.left = self.put_(node.left, a, b)
		elif a > node.midpoint:
			node.right = self.put_(node.right, a, b)
		else:
			node.putInterval(a, b)
		return node

	def getCrossCount(self, a, b):
		return self.getCrossCount_(self.root, a, b)

	def getCrossCount_(self, node, a, b):
		if node is None:
			return 0
		result = node.getCrossCount(a, b)
		if a < node.midpoint:
			result += self.getCrossCount_(node.left, a, min(b, node.midpoint))
		if b > node.midpoint:
			result += self.getCrossCount_(node.right, max(a, node.midpoint), b)
		return result
tree = IntervalTree()
(N, M) = map(int, input().split())
for _ in range(N):
	(a, b) = map(int, input().split())
	tree.put(a, b)
res = 0
for _ in range(M):
	(c, d) = map(int, input().split())
	res += tree.getCrossCount(c, d)
print(res)


from bisect import bisect_left, bisect_right

def binary_search_high(search_space, data):
	(low, high) = (0, len(search_space) - 1)
	while low <= high:
		mid = int((low + high) / 2)
		if search_space[mid] == data:
			while mid <= high and search_space[mid] == data:
				mid += 1
			return mid - 1
		if mid + 1 <= high and search_space[mid] < data and (search_space[mid + 1] > data):
			return mid
		elif search_space[mid] < data:
			low = mid + 1
		else:
			high = mid - 1
	return high

def binary_search_low(search_space, data):
	(low, high) = (0, len(search_space) - 1)
	while low <= high:
		mid = int((low + high) / 2)
		if search_space[mid] == data:
			while mid <= high and search_space[mid] == data:
				mid -= 1
			return mid
		if mid + 1 <= high and search_space[mid] < data and (search_space[mid + 1] >= data):
			return mid
		elif search_space[mid] < data:
			low = mid + 1
		else:
			high = mid - 1
	return high

def search(l, h, low, high):
	(count_l, count_r) = (1, 1)
	count_l += binary_search_high(low, h)
	count_r += binary_search_low(high, l)
	return 0 if count_l - count_r < 0 else count_l - count_r
data = input().split(' ')
N = int(data[0])
M = int(data[1])
low = []
high = []
for i in range(N):
	data = input().split(' ')
	data[0] = int(data[0])
	data[1] = int(data[1])
	low.append(data[0] if data[0] < data[1] else data[1])
	high.append(data[0] if data[0] > data[1] else data[1])
low = sorted(low)
high = sorted(high)
count = 0
for i in range(M):
	data = input().split(' ')
	data[0] = int(data[0])
	data[1] = int(data[1])
	l = data[0] if data[0] < data[1] else data[1]
	h = data[0] if data[0] > data[1] else data[1]
	count += search(l, h, low, high)
print(count)


(n, m) = (int(x) for x in input().split())
priority = {0: 'start throwing', 1: 'start catching', 2: 'end catching', 3: 'end throwing'}
array = []
for _ in range(n):
	(start, end) = [int(x) for x in input().split()]
	array.append((1, start))
	array.append((2, end))
for _ in range(m):
	(start, end) = [int(x) for x in input().split()]
	array.append((0, start))
	array.append((3, end))
array = sorted(array, key=lambda x: (x[1], x[0]))
count = active = active_spots = 0
for (action, value) in array:
	action = priority[action]
	if action == 'start throwing':
		active += 1
		count += active_spots
	if action == 'start catching':
		count += active
		active_spots += 1
	if action == 'end catching':
		active_spots -= 1
	if action == 'end throwing':
		active -= 1
print(count)


READ_FROM_FILE = False
DEBUG = False
if READ_FROM_FILE:
	f = open('input.txt')
	inp = f.readline
else:
	inp = input
(n, m) = [int(x) for x in inp().strip().split()]

class ptype:
	shot_begin = 0
	shot_end = 1
	player_begin = 2
	player_end = 3
shots_begins = []
shots_ends = []
for _ in range(n):
	(x, y) = map(int, inp().strip().split())
	shots_begins.append((x, ptype.shot_begin))
	shots_ends.append((y, ptype.shot_end))
players_begins = []
players_ends = []
for _ in range(m):
	(x, y) = map(int, inp().strip().split())
	players_begins.append((x, ptype.player_begin))
	players_ends.append((y, ptype.player_end))
all_points = []
all_points.extend(players_begins)
all_points.extend(shots_begins)
all_points.extend(players_ends)
all_points.extend(shots_ends)
all_points = sorted(all_points, key=lambda x: x[0])
if DEBUG:
	print(all_points)
shots = players = c = 0
for point in all_points:
	if point[1] == ptype.shot_begin:
		shots += 1
		c += players
	elif point[1] == ptype.shot_end:
		shots -= 1
	elif point[1] == ptype.player_begin:
		players += 1
		c += shots
	elif point[1] == ptype.player_end:
		players -= 1
print(c)


def readcase():
	(ablen, cdlen) = readints()
	(a, b) = readivals(ablen)
	(c, d) = readivals(cdlen)
	return (a, b, c, d)

def readivals(ilen):
	(a, b) = ([], [])
	for i in range(ilen):
		(aelt, belt) = readints()
		a.append(aelt)
		b.append(belt)
	return (a, b)

def readints():
	return [int(fld) for fld in input().strip().split()]

def main():
	(a, b, c, d) = readcase()
	acount = ccount = 0

	def aseen():
		nonlocal acount
		acount += 1
		return ccount

	def cseen():
		nonlocal ccount
		ccount += 1
		return acount

	def bseen():
		nonlocal acount
		acount -= 1
		return 0

	def dseen():
		nonlocal ccount
		ccount -= 1
		return 0
	actionf = [aseen, cseen, bseen, dseen]
	action = sorted([(e, 0) for e in a] + [(e, 1) for e in c] + [(e, 2) for e in b] + [(e, 3) for e in d])
	ans = 0
	for (pos, act) in action:
		ans += actionf[act]()
	print(ans)
main()


from bisect import bisect_left, bisect_right
from collections import defaultdict

def read():
	return [int(v) for v in input().split()]
shots = defaultdict(list)
total = 0
(n, m) = read()
(start, end) = map(sorted, zip(*(read() for _ in range(n))))
for (c, d) in [read() for _ in range(m)]:
	total += bisect_right(start, d) - bisect_left(end, c)
print(total)


(N, M) = [int(x) for x in input().split()]
events = []
shot_in = 1
player_in = 2
shot_out = 3
player_out = 4
for _ in range(N):
	shot = [int(x) for x in input().split()]
	events.append((shot[0], shot_in))
	events.append((shot[1], shot_out))
for _ in range(M):
	player = [int(x) for x in input().split()]
	events.append((player[0], player_in))
	events.append((player[1], player_out))
events.sort()
shots = 0
players = 0
strength = 0
for (dist, etype) in events:
	if etype == shot_in:
		shots += 1
		strength += players
	elif etype == shot_out:
		shots -= 1
	elif etype == player_in:
		players += 1
		strength += shots
	else:
		players -= 1
print(strength)


import sys
(n, m) = map(int, input().split())
t1 = [0] * 100010
t2 = [0] * 100010
tt = int(0)
for i in range(n):
	(l, r) = map(int, input().split())
	t1[l] += 1
	t2[r + 1] -= 1
for i in range(1, 100010):
	t1[i] += t1[i - 1]
	t2[i] += t2[i - 1]
for i in range(m):
	(l, r) = map(int, input().split())
	tt += t1[r] + t2[l]
print(tt)


(n, m) = map(int, input().split())
shots = [list(map(int, input().split())) for _ in range(n)]
begins = sorted([s[0] for s in shots])
ends = sorted([s[1] for s in shots])
opponents = [list(map(int, input().split())) for _ in range(m)]

def log_find(index_start, index_stop, tab, value):
	while index_stop - index_start > 1:
		mid = (index_stop + index_start) // 2
		if tab[mid] < value:
			index_start = mid
		else:
			index_stop = mid
	return index_stop
result = 0
for (a, b) in opponents:
	c1 = log_find(-1, len(ends), ends, a)
	c2 = log_find(-1, len(begins), begins, b + 1)
	result += c2 - c1
print(result)


def solve():
	(n, m) = map(int, input().split())
	t1 = [0] * 100010
	t2 = [0] * 100010
	tt = int(0)
	for i in range(n):
		(l, r) = map(int, input().split())
		t1[l] += 1
		t2[r + 1] -= 1
	for i in range(1, 100010):
		t1[i] += t1[i - 1]
		t2[i] += t2[i - 1]
	for i in range(m):
		(l, r) = map(int, input().split())
		tt += t1[r] + t2[l]
	print(tt)
solve()


import sys
import os
firstLine = input().split()
N = int(firstLine[0])
M = int(firstLine[1])
maxVal = 1000000
tally1 = [0] * maxVal
tally2 = [0] * maxVal
for i in range(0, N):
	line = input().split()
	tally1[int(line[0])] += 1
	tally2[int(line[1]) + 1] -= 1
for i in range(1, maxVal):
	tally1[i] += tally1[i - 1]
	tally2[i] += tally2[i - 1]
sumStrengths = 0
for j in range(0, M):
	player = input().split()
	playerStart = int(player[0])
	playerEnd = int(player[1])
	sumStrengths += tally1[playerEnd] + tally2[playerStart]
print(sumStrengths)


(N, M) = map(int, input().split())
ranges = []
for _ in range(N):
	(a, b) = map(int, input().split())
	ranges.append((a, -1, 0))
	ranges.append((b, 1, 0))
for _ in range(M):
	(a, b) = map(int, input().split())
	ranges.append((a, -1, 1))
	ranges.append((b, 1, 1))
ranges = sorted(ranges)
(score, A) = (0, [0, 0])
for (a, i, p) in ranges:
	if i == -1:
		A[p] += 1
		score += A[1 - p]
	else:
		A[p] -= 1
print(score)


import sys
import bisect

def find_le(a, x):
	i = bisect.bisect_right(a, x)
	if i:
		return i - 1
	raise ValueError

def find_ge(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a):
		return i
	raise ValueError

def find_gt(a, x):
	i = bisect.bisect_right(a, x)
	if i != len(a):
		return i
	raise ValueError

def find_lt(a, x):
	i = bisect.bisect_left(a, x)
	if i:
		return i - 1
	raise ValueError
fname = ''
if fname != '':
	fh = open(fname, 'r')
else:
	fh = sys.stdin
(N, M) = [int(a) for a in fh.readline().strip().split()]
cricketerA = []
cricketerB = []
for _ in range(N):
	(A, B) = [int(a) for a in fh.readline().strip().split()]
	cricketerA.append(A)
	cricketerB.append(B)
Left = sorted(cricketerA)
Right = sorted(cricketerB)
cnt = 0
for _ in range(M):
	(C, D) = [int(a) for a in fh.readline().strip().split()]
	try:
		indC = find_ge(Right, C)
	except ValueError as v:
		indC = N
	try:
		indD = find_le(Left, D)
	except ValueError as v:
		indD = 0
	cnt += indD - indC + 1
print(cnt)


(n, m) = map(int, input().split())
t1 = [0] * 100010
t2 = [0] * 100010
tt = int(0)
for i in range(n):
	(l, r) = map(int, input().split())
	t1[l] += 1
	t2[r + 1] -= 1
for i in range(1, 100010):
	t1[i] += t1[i - 1]
	t2[i] += t2[i - 1]
for i in range(m):
	(l, r) = map(int, input().split())
	tt += t1[r] + t2[l]
print(tt)


__author__ = 'Ward'
import sys
import bisect
(N, M) = map(int, sys.stdin.readline().split())
A = [0] * N
B = [0] * N
C = [0] * M
D = [0] * M
for i in range(0, N):
	(A[i], B[i]) = map(int, sys.stdin.readline().split())
for i in range(0, M):
	(C[i], D[i]) = map(int, sys.stdin.readline().split())
A.sort()
B.sort()
Ans = M * N
for d in D:
	Ans -= len(A) - bisect.bisect_right(A, d)
for c in C:
	Ans -= bisect.bisect_left(B, c)
print(Ans)


from sys import stdin
from bisect import bisect

def readInts():
	return map(int, stdin.readline().strip().split())

def count_overlap(n, starts, ends, bl, br):
	pre = bisect(ends, bl - 1)
	post_inv = bisect(starts, br)
	post = n - post_inv
	ovl = n - pre - post
	return ovl
(n, m) = readInts()
starts = []
ends = []
for _ in range(n):
	(start, end) = readInts()
	starts.append(start)
	ends.append(end)
starts.sort()
ends.sort()
tot = 0
for _ in range(m):
	(bl, br) = readInts()
	tot += count_overlap(n, starts, ends, bl, br)
print(tot)


[n, m] = map(int, input().strip().split())
s = []
(a, b) = ({}, {})
for _ in range(n):
	[p, q] = map(int, input().strip().split())
	s.append([p, 1])
	a[p] = a.get(p, 0) + 1
	a[q + 1] = a.get(q + 1, 0) - 1
qu = []
for _ in range(m):
	[p, q] = map(int, input().strip().split())
	a[p] = a.get(p, 0)
	s.append([p, 0])
	s.append([q, 0])
	qu.append([p, q])
s = sorted(s)
t = 0
for (p, c) in s:
	t += c
	b[p] = t
t = 0
for k in sorted(a):
	t += a[k]
	a[k] = t
ans = 0
for (p, q) in qu:
	ans += a[p] + b[q] - b[p]
print(ans)


(n, m) = map(int, input().split())
t1 = [0] * 100010
t2 = [0] * 100010
tt = int(0)
for i in range(n):
	(l, r) = map(int, input().split())
	t1[l] += 1
	t2[r + 1] -= 1
for i in range(1, 100010):
	t1[i] += t1[i - 1]
	t2[i] += t2[i - 1]
for i in range(m):
	(l, r) = map(int, input().split())
	tt += t1[r] + t2[l]
print(tt)


import sys
from collections import defaultdict
from itertools import accumulate
from bisect import bisect_left, bisect_right
(n, m) = [int(x) for x in input().strip().split(' ')]
S = defaultdict(int)
E = defaultdict(int)
for _ in range(n):
	(a, b) = [int(x) - 1 for x in input().strip().split(' ')]
	S[a] += 1
	E[b + 1] -= 1
S = sorted(S.items(), key=lambda p: p[0])
E = sorted(E.items(), key=lambda p: p[0])
S = list(accumulate(S, lambda x, y: (y[0], y[1] + x[1])))
E = list(accumulate(E, lambda x, y: (y[0], y[1] + x[1])))
total = 0
for _ in range(m):
	(c, d) = [int(x) - 1 for x in input().strip().split(' ')]
	if d < S[0][0] or c > E[-1][0]:
		continue
	if c < E[0][0]:
		cs = 0
	else:
		s = bisect_right(E, (c, sys.maxsize))
		cs = E[s - 1][1]
	if d >= S[-1][0]:
		ce = S[-1][1]
	else:
		e = bisect_right(S, (d, sys.maxsize))
		ce = S[e - 1][1]
	total += cs + ce
print(total)


from bisect import bisect_left, bisect_right

def list_input():
	return list(map(int, input().strip().split()))

def add(bit, idx):
	lim = len(bit)
	while idx < lim:
		bit[idx] += 1
		idx += idx & -idx

def get(bit, idx):
	res = 0
	while idx > 0:
		res += bit[idx]
		idx -= idx & -idx
	return res
(N, M) = list_input()
shots = list()
distances = set()
for _ in range(N):
	(shot_fr, shot_to) = list_input()
	distances.add(shot_fr)
	distances.add(shot_to)
	shots.append((shot_fr, shot_to))
idx2dist = [0]
dist2idx = dict()
for (i, dist) in enumerate(sorted(distances), 1):
	idx2dist.append(dist)
	dist2idx[dist] = i
lbnd_fenwick = [0] * len(idx2dist)
rbnd_fenwick = [0] * len(idx2dist)
for (shot_fr, shot_to) in shots:
	(idx_fr, idx_to) = (dist2idx[shot_fr], dist2idx[shot_to])
	add(lbnd_fenwick, idx_fr)
	add(rbnd_fenwick, idx_to)
res = 0
for _ in range(M):
	(fr, to) = list_input()
	res += get(lbnd_fenwick, bisect_right(idx2dist, to) - 1)
	res -= get(rbnd_fenwick, bisect_left(idx2dist, fr) - 1)
print(res)


import bisect
(N, M) = map(int, input().split())
A = []
B = []
for n in range(N):
	(x, y) = map(int, input().split())
	A.append(x)
	B.append(y)
A.sort()
B.sort()
tot = 0
for n in range(M):
	(c, d) = map(int, input().split())
	i = bisect.bisect_right(A, d)
	j = bisect.bisect_left(B, c)
	tot += i - j
print(tot)


(shots, players) = [int(i) for i in input().split()]
tree1 = [0 for i in range(1000000)]
tree2 = [0 for i in range(1000000)]

def update(tree, x, val):
	while x <= 1000000:
		tree[x - 1] += val
		x += x & -x

def suma(tree, x):
	suma = 0
	while x > 0:
		suma += tree[x - 1]
		x -= x & -x
	return suma
for shot in range(shots):
	rango = [int(i) for i in input().split()]
	update(tree1, rango[0], 1)
	update(tree2, rango[1], 1)
strengths = 0
for player in range(players):
	rango = [int(i) for i in input().split()]
	a = suma(tree2, rango[0] - 1)
	b = suma(tree1, rango[1])
	strengths += b - a
print(strengths)


import sys
(n, m) = [int(temp) for temp in input().strip().split(' ')]
shots = [[int(temp) for temp in input().strip().split(' ')] for _ in range(n)]
players = [[int(temp) for temp in input().strip().split(' ')] for _ in range(m)]
shot_starts = sorted([shot[0] for shot in shots]) + [sys.maxsize]
shot_ends = sorted([shot[1] for shot in shots]) + [sys.maxsize]
player_starts = sorted([player[0] for player in players]) + [sys.maxsize]
player_ends = sorted([player[1] for player in players]) + [sys.maxsize]
i = 0
j = 0
x = 0
y = 0
player_counts = 0
shot_counts = 0
score = 0
for _ in range(2 * n + 2 * m):
	action_options = [shot_starts[i], player_starts[x], shot_ends[j], player_ends[y]]
	(action, _) = min(enumerate(action_options), key=lambda x: x[1])
	if action == 0:
		i += 1
		shot_counts += 1
		score += player_counts
	elif action == 1:
		x += 1
		player_counts += 1
		score += shot_counts
	elif action == 2:
		j += 1
		shot_counts -= 1
	else:
		y += 1
		player_counts -= 1
print(score)


import operator
import functools
(N, M) = [int(x) for x in input().strip().split()]
times = []
starts = []
events = []
for n in range(N):
	(a, b) = [int(x) for x in input().strip().split()]
	times.append(a)
	times.append(b + 1)
	starts.append(a)
	events.append((a, True))
	events.append((b + 1, False))

def cmp_events(x, y):
	if x[0] < y[0]:
		return -1
	elif x[0] > y[0]:
		return 1
	elif x[1] and (not y[1]):
		return 1
	elif not x[1] and y[1]:
		return -1
	else:
		return 0
events = sorted(events, key=functools.cmp_to_key(cmp_events))
times = sorted(times)
starts = sorted(starts)
ranges = 0
range_count = []
for event in events:
	if event[1]:
		ranges += 1
	else:
		ranges -= 1
	range_count.append(ranges)

def bin_search(x, arr):

	def bin_search_help(l, r):
		if r - l == 1:
			return l
		mid = (r + l) // 2
		if arr[mid] <= x:
			return bin_search_help(mid, r)
		else:
			return bin_search_help(l, mid)
	return bin_search_help(0, len(arr))
total = 0
for m in range(M):
	(c, d) = [int(x) for x in input().strip().split()]
	idx = bin_search(c, times)
	n_ranges = range_count[idx]
	idx2 = bin_search(d, times)
	s_idx = bin_search(c, starts)
	s_idx2 = bin_search(d, starts)
	n_new = s_idx2 - s_idx
	total += n_ranges + n_new
print(total)


(n, m) = map(int, input().split())
t1 = [0] * 100010
t2 = [0] * 100010
tt = int(0)
for i in range(n):
	(l, r) = map(int, input().split())
	t1[l] += 1
	t2[r + 1] -= 1
for i in range(1, 100010):
	t1[i] += t1[i - 1]
	t2[i] += t2[i - 1]
for i in range(m):
	(l, r) = map(int, input().split())
	tt += t1[r] + t2[l]
print(tt)


import bisect

def player_strength(player, starts, ends):
	not_high_shots = bisect.bisect_right(starts, player[1])
	low_shots = bisect.bisect_left(ends, player[0])
	return not_high_shots - low_shots
(num_shots, num_players) = map(int, input().strip().split())
shots = [tuple(map(int, input().strip().split())) for i in range(num_shots)]
players = [tuple(map(int, input().strip().split())) for i in range(num_players)]
(unsorted_starts, unsorted_ends) = zip(*shots)
starts = sorted(unsorted_starts)
ends = sorted(unsorted_ends)
print(sum((player_strength(player, starts, ends) for player in players)))


(n, m) = map(int, input().split())
t1 = [0] * 100010
t2 = [0] * 100010
tt = int(0)
for i in range(n):
	(l, r) = map(int, input().split())
	t1[l] += 1
	t2[r + 1] -= 1
for i in range(1, 100010):
	t1[i] += t1[i - 1]
	t2[i] += t2[i - 1]
for i in range(m):
	(l, r) = map(int, input().split())
	tt += t1[r] + t2[l]
print(tt)


import sys

def sort(l):
	if len(l) == 1:
		return l
	mid = len(l) // 2
	left = sort(l[:mid])
	right = sort(l[mid:])
	return merge(left, right)

def merge(left, right):
	result = []
	while left and right:
		if left[0] <= right[0]:
			result.append(left[0])
			del left[0]
		else:
			result.append(right[0])
			del right[0]
	if left:
		result += left
	if right:
		result += right
	return result

def indexofclosest(point, arr):
	if point < arr[0]:
		return 0
	if point > arr[-1]:
		return len(arr)
	high = len(arr) - 1
	low = 0
	while low <= high:
		mid = (low + high) // 2
		if point == arr[mid]:
			return mid + 1
		if point < arr[mid]:
			high = mid - 1
		elif point > arr[mid]:
			low = mid + 1
	return max(low, high)
(n, m) = map(int, input().strip().split(' '))
t1 = [0] * 100010
t2 = [0] * 100010
tt = int(0)
for i in range(n):
	(l, r) = map(int, input().split())
	t1[l] += 1
	t2[r + 1] -= 1
for i in range(1, 100010):
	t1[i] += t1[i - 1]
	t2[i] += t2[i - 1]
for i in range(m):
	(l, r) = map(int, input().split())
	tt += t1[r] + t2[l]
print(tt)


from operator import itemgetter
import bisect
(n, m) = list(map(int, input().strip().split()))
mrx_sorted_by_left = []
for i in range(n):
	(a, b) = list(map(int, input().strip().split()))
	where = bisect.bisect(mrx_sorted_by_left, (a, b))
	mrx_sorted_by_left.insert(where, (a, b))
iter_mrx_sorted_by_left = iter(mrx_sorted_by_left)
mrx_sorted_by_right = [next(iter_mrx_sorted_by_left)[1]]
(starts, ends) = zip(*mrx_sorted_by_left)
shots_sorted_by_right = []
for i in range(m):
	(c, d) = list(map(int, input().strip().split()))
	where = bisect.bisect(shots_sorted_by_right, (d, c))
	shots_sorted_by_right.insert(where, (d, c))
stopped = 0
for i in range(m):
	(d, c) = shots_sorted_by_right[i]
	start_before_shot_ends = bisect.bisect(starts, d)
	while len(mrx_sorted_by_right) < start_before_shot_ends:
		try:
			bisect.insort(mrx_sorted_by_right, next(iter_mrx_sorted_by_left)[1])
		except StopIteration:
			pass
	where = len(mrx_sorted_by_right) - bisect.bisect_left(mrx_sorted_by_right, c)
	stopped += where
print(stopped)


(n, m) = map(int, input().split())
t1 = [0] * 100010
t2 = [0] * 100010
tt = int(0)
for i in range(n):
	(l, r) = map(int, input().split())
	t1[l] += 1
	t2[r + 1] -= 1
for i in range(1, 100010):
	t1[i] += t1[i - 1]
	t2[i] += t2[i - 1]
for i in range(m):
	(l, r) = map(int, input().split())
	tt += t1[r] + t2[l]
print(tt)


(n, m) = map(int, input().split())
from collections import defaultdict
t1 = defaultdict(int)
t2 = defaultdict(int)
tt = 0
for i in range(n):
	(l, r) = map(int, input().split())
	t1[l] += 1
	t2[r + 1] -= 1
for i in range(1, 100010):
	t1[i] += t1[i - 1]
	t2[i] += t2[i - 1]
for i in range(m):
	(l, r) = map(int, input().split())
	tt += t1[r] + t2[l]
print(tt)


(n, m) = map(int, input().split())
t1 = [0] * 100010
t2 = [0] * 100010
tt = int(0)
for i in range(n):
	(l, r) = map(int, input().split())
	t1[l] += 1
	t2[r + 1] -= 1
for i in range(1, 100010):
	t1[i] += t1[i - 1]
	t2[i] += t2[i - 1]
for i in range(m):
	(l, r) = map(int, input().split())
	tt += t1[r] + t2[l]
print(tt)


(n, m) = map(int, input().split())
t1 = [0] * 100010
t2 = [0] * 100010
tt = int(0)
for i in range(n):
	(l, r) = map(int, input().split())
	t1[l] += 1
	t2[r + 1] -= 1
for i in range(1, 100010):
	t1[i] += t1[i - 1]
	t2[i] += t2[i - 1]
for i in range(m):
	(l, r) = map(int, input().split())
	tt += t1[r] + t2[l]
print(tt)


import sys
from time import time
import bisect

def solve(uu, vv):
	uu.sort()
	vv.sort()
	uu2 = sorted(uu, key=lambda u: u[::-1])
	print('uu=%s\nuu2=%s\nvv=%s' % (uu, uu2, vv), file=sys.stderr)
	ff = [fr for (fr, _) in uu]
	tt = [to for (_, to) in uu2]
	sm = 0
	for (fr, to) in vv:
		ix1 = bisect.bisect_left(ff, fr)
		ix2 = bisect.bisect_right(ff, to)
		ix3 = bisect.bisect_left(tt, fr)
		ix4 = bisect.bisect_right(tt, to)
		print('\tfr=%d to=%d ix1=%d ix2=%d ix3=%d ix4=%d' % (fr, to, ix1, ix2, ix3, ix4), file=sys.stderr)
		sm += max(ix2, ix4) - min(ix1, ix3)
	return sm
tm = time()
(n, m) = map(int, input().split())
(uu, vv) = ([], [])
for _ in range(n):
	(fr, to) = map(int, input().split())
	uu.append((fr, to))
for _ in range(m):
	(fr, to) = map(int, input().split())
	vv.append((fr, to))
print(solve(uu, vv))
print('time elapsed: %s' % (time() - tm,), file=sys.stderr)


import os
import sys
import math

def binrank(ll, start, end, x):
	if start == end:
		return start
	mid = int(math.ceil((start + end) / 2.0))
	if x >= ll[mid]:
		start = mid
	if x < ll[mid]:
		end = mid - 1
	return binrank(ll, start, end, x)

def strength(a, b):
	l_shots = sorted([i[0] for i in a])
	r_shots = sorted([i[1] for i in a])
	tot = len(l_shots)
	scores = []
	for (x, y) in b:
		if x - 0.5 < r_shots[0]:
			s1 = 0
		else:
			s1 = binrank(r_shots, 0, tot - 1, x - 0.5) + 1
		if y < l_shots[0]:
			s2 = 0
		else:
			s2 = tot - 1 - binrank(l_shots, 0, tot - 1, y)
		scores += [tot - (s1 + s2)]
	return sum(scores)
(n, m) = map(int, input().split())
a = []
b = []
c = 0
for _ in range(n):
	a.append(list(map(int, input().rstrip().split())))
for _ in range(m):
	b.append(list(map(int, input().rstrip().split())))
print(strength(a, b))


import math

def binrank(ll, start, end, x):
	if start == end:
		return start
	mid = int(math.ceil((start + end) / 2.0))
	if x >= ll[mid]:
		start = mid
	if x < ll[mid]:
		end = mid - 1
	return binrank(ll, start, end, x)

def solve(shots, players):
	lshots = sorted([a[0] for a in shots])
	rshots = sorted([a[1] for a in shots])
	sl = len(lshots)
	scores = []
	for (x, y) in players:
		if x - 0.5 < rshots[0]:
			miss1 = 0
		else:
			miss1 = binrank(rshots, 0, sl - 1, x - 0.5) + 1
		if y < lshots[0]:
			miss2 = 0
		else:
			miss2 = sl - 1 - binrank(lshots, 0, sl - 1, y)
		scores += [sl - (miss1 + miss2)]
	return sum(scores)
nm = input().split()
n = int(nm[0])
m = int(nm[1])
shots = []
for _ in range(n):
	shots.append(list(map(int, input().rstrip().split())))
players = []
for _ in range(m):
	players.append(list(map(int, input().rstrip().split())))
total = 0
result = solve(shots, players)
print(str(result))


(n, m) = map(int, input().split())
ns = list((tuple(map(int, input().split())) for _ in range(n)))
ms = list((tuple(map(int, input().split())) for _ in range(m)))
score = [0] * m
i = 0
ns.sort(key=lambda x: x[0])
ms.sort(key=lambda x: x[1])
for (k, (c, d)) in enumerate(ms):
	while i < len(ns) and ns[i][0] <= d:
		i += 1
	score[k] += i
i = 0
ns.sort(key=lambda x: x[1])
ms.sort(key=lambda x: x[0])
for (k, (c, d)) in enumerate(ms):
	while i < len(ns) and ns[i][1] < c:
		i += 1
	score[k] -= i
print(sum(score))


from bisect import bisect_left, bisect_right

def solve(a, b, c, d):
	return sum((bisect_right(c, v) for v in b)) - sum((bisect_left(d, u) for u in a))
(n, m) = map(int, input().split())
((a, b), (c, d)) = (zip(*(map(int, input().split()) for _ in range(k))) for k in (n, m))
print(solve(a, b, sorted(c), sorted(d)))


(n, m) = map(int, input().split())
t1 = [0] * 100010
t2 = [0] * 100010
tt = int(0)
for i in range(n):
	(l, r) = map(int, input().split())
	t1[l] += 1
	t2[r + 1] -= 1
for i in range(1, 100010):
	t1[i] += t1[i - 1]
	t2[i] += t2[i - 1]
for i in range(m):
	(l, r) = map(int, input().split())
	tt += t1[r] + t2[l]
print(tt)


import os
import sys
import math

def binrank(ll, start, end, x):
	if start == end:
		return start
	mid = int(math.ceil((start + end) / 2.0))
	if x >= ll[mid]:
		start = mid
	if x < ll[mid]:
		end = mid - 1
	return binrank(ll, start, end, x)

def solve(shots, players):
	lshots = sorted([a[0] for a in shots])
	rshots = sorted([a[1] for a in shots])
	sl = len(lshots)
	scores = []
	for (x, y) in players:
		if x - 0.5 < rshots[0]:
			miss1 = 0
		else:
			miss1 = binrank(rshots, 0, sl - 1, x - 0.5) + 1
		if y < lshots[0]:
			miss2 = 0
		else:
			miss2 = sl - 1 - binrank(lshots, 0, sl - 1, y)
		scores += [sl - (miss1 + miss2)]
	return sum(scores)
nm = input().split()
n = int(nm[0])
m = int(nm[1])
shots = []
for _ in range(n):
	shots.append(list(map(int, input().rstrip().split())))
players = []
for _ in range(m):
	players.append(list(map(int, input().rstrip().split())))
result = solve(shots, players)
print(result)


import sys

def rl(proc=None):
	if proc is not None:
		return proc(sys.stdin.readline())
	else:
		return sys.stdin.readline().rstrip()

def srl(proc=None):
	if proc is not None:
		return list(map(proc, rl().split()))
	else:
		return rl().split()
OPEN_X = 1
CLOSE_X = 2
OPEN_P = 0
CLOSE_P = 3

def main():
	(N, M) = srl(int)
	ev = []
	for _ in range(N):
		(a, b) = srl(int)
		ev.append((a, OPEN_X))
		ev.append((b, CLOSE_X))
	for _ in range(M):
		(a, b) = srl(int)
		ev.append((a, OPEN_P))
		ev.append((b, CLOSE_P))
	n_pla = 0
	n_shots = 0
	ret = 0
	ev.sort()
	for (_, e) in ev:
		if e == OPEN_X:
			ret += n_pla
			n_shots += 1
		elif e == OPEN_P:
			ret += n_shots
			n_pla += 1
		elif e == CLOSE_P:
			n_pla -= 1
		elif e == CLOSE_X:
			n_shots -= 1
	print(ret)
main()


(n, m) = map(int, input().split())
t1 = [0] * 100010
t2 = [0] * 100010
tt = int(0)
for i in range(n):
	(l, r) = map(int, input().split())
	t1[l] += 1
	t2[r + 1] -= 1
for i in range(1, 100010):
	t1[i] += t1[i - 1]
	t2[i] += t2[i - 1]
for i in range(m):
	(l, r) = map(int, input().split())
	tt += t1[r] + t2[l]
print(tt)


from bisect import bisect_left, bisect_right

def solve(a, b, c, d):
	return sum((bisect_right(c, v) for v in b)) - sum((bisect_left(d, u) for u in a))
((a, b), (c, d)) = (zip(*(map(int, input().split()) for _ in range(k))) for k in map(int, input().split()))
print(solve(a, b, sorted(c), sorted(d)))


from bisect import bisect_left, bisect_right

def solve(a, b, c, d):
	return sum((bisect_right(c, v) for v in b)) - sum((bisect_left(d, u) for u in a))
((a, b), (c, d)) = (zip(*(map(int, input().split()) for _ in range(k))) for k in map(int, input().split()))
print(solve(a, b, sorted(c), sorted(d)))


(n, m) = map(int, input().split())
t1 = [0] * 100010
t2 = [0] * 100010
tt = int(0)
for i in range(n):
	(l, r) = map(int, input().split())
	t1[l] += 1
	t2[r + 1] -= 1
for i in range(1, 100010):
	t1[i] += t1[i - 1]
	t2[i] += t2[i - 1]
for i in range(m):
	(l, r) = map(int, input().split())
	tt += t1[r] + t2[l]
print(tt)


from bisect import bisect_left, bisect_right

def solve(a, b, c, d):
	return sum((bisect_right(c, v) for v in b)) - sum((bisect_left(d, u) for u in a))
((a, b), (c, d)) = (zip(*(map(int, input().split()) for _ in range(k))) for k in map(int, input().split()))
print(solve(a, b, sorted(c), sorted(d)))


import os
import sys
from bisect import bisect_left, bisect_right

def solve(s_b, s_e, p_b, p_e):
	return sum((bisect_right(p_b, v) - bisect_left(p_e, u) for (v, u) in zip(s_e, s_b)))
(n, m) = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n + m)]
((s_b, s_e), (p_b, p_e)) = (zip(*arr[:n]), zip(*arr[n:]))
print(solve(s_b, s_e, sorted(p_b), sorted(p_e)))


from bisect import bisect_left, bisect_right

def solve(a, b, c, d):
	return sum((bisect_right(c, v) for v in b)) - sum((bisect_left(d, u) for u in a))
((a, b), (c, d)) = (zip(*(map(int, input().split()) for _ in range(k))) for k in map(int, input().split()))
print(solve(a, b, sorted(c), sorted(d)))


import bisect
from collections import defaultdict
(n, m) = map(int, input().split())
epoch = set()

def call():
	d = {0: [], 1: []}
	return d
d = defaultdict(call)
for _ in range(n):
	(i, j) = map(int, input().split())
	d[i][0].append((i, j, 0))
	d[j][1].append((i, j, 0))
	epoch.add(i)
	epoch.add(j)
total = 0
for _ in range(m):
	(i, j) = map(int, input().split())
	d[i][0].append((i, j, 1))
	d[j][1].append((i, j, 1))
	epoch.add(i)
	epoch.add(j)
epoch = sorted(list(epoch))
cs = 0
cp = 0
tots = 0
for it in epoch:
	starts = d[it][0]
	ends = d[it][1]
	for each in starts:
		(s, e, st) = each
		if st == 0:
			cs += 1
			tots += cp
		if st == 1:
			cp += 1
			tots += cs
	for each in ends:
		(s, e, st) = each
		if st == 0:
			cs -= 1
		if st == 1:
			cp -= 1
print(tots)


from bisect import bisect_left, bisect_right

def solve(a, b, c, d):
	return sum((bisect_right(c, v) for v in b)) - sum((bisect_left(d, u) for u in a))
((a, b), (c, d)) = (zip(*(map(int, input().split()) for _ in range(k))) for k in map(int, input().split()))
print(solve(a, b, sorted(c), sorted(d)))


(n, m) = map(int, input().split())
t1 = [0] * 100010
t2 = [0] * 100010
tt = int(0)
for i in range(n):
	(l, r) = map(int, input().split())
	t1[l] += 1
	t2[r + 1] -= 1
for i in range(1, 100010):
	t1[i] += t1[i - 1]
	t2[i] += t2[i - 1]
for i in range(m):
	(l, r) = map(int, input().split())
	tt += t1[r] + t2[l]
print(tt)