Mike and Geometry Problem (Codeforces 689E)
Tags: Implement, geometry

Mike wants to prepare for IMO but he doesn't know geometry, so his teacher gave him an interesting geometry problem. Let's define f([l, r]) = r - l + 1 to be the number of integer points in the segment [l, r] with l ≤ r (say that ). You are given two integers n and k and n closed intervals [li, ri] on OX axis and you have to find:  In other words, you should find the sum of the number of integer points in the intersection of any k of the segments. As the answer may be very large, output it modulo 1000000007 (109 + 7).Mike can't solve this problem so he needs your help. You will help him, won't you? 

Input: The first line contains two integers n and k (1 ≤ k ≤ n ≤ 200 000) — the number of segments and the number of segments in intersection groups respectively.Then n lines follow, the i-th line contains two integers li, ri ( - 109 ≤ li ≤ ri ≤ 109), describing i-th segment bounds.

Output: Print one integer number — the answer to Mike's problem modulo 1000000007 (109 + 7) in the only line.

Note: In the first example: ;;.So the answer is 2 + 1 + 2 = 5.

Sample Inputs:
3 2
1 2
1 3
2 3

3 3
1 3
1 3
1 3

3 1
1 2
2 3
3 4

Sample Outputs:
5

3

6

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def comb(n, r):
    return fact[n] * inv[r] % mod * inv[n - r] % mod if n >= r >= 0 else 0
(n, k) = map(int, input().split())
mod = pow(10, 9) + 7
l = n + 5
fact = [1] * (l + 1)
for i in range(1, l + 1):
    fact[i] = i * fact[i - 1] % mod
inv = [1] * (l + 1)
inv[l] = pow(fact[l], mod - 2, mod)
for i in range(l - 1, -1, -1):
    inv[i] = (i + 1) * inv[i + 1] % mod
lr = [tuple(map(int, input().split())) for _ in range(n)]
s = set()
for (l, r) in lr:
    s.add(l)
    s.add(r + 1)
s = list(s)
s.sort()
d = dict()
m = len(s)
for i in range(m):
    d[s[i]] = i
cnt = [0] * m
for (l, r) in lr:
    cnt[d[l]] += 1
    cnt[d[r + 1]] -= 1
for i in range(1, m):
    cnt[i] += cnt[i - 1]
ans = 0
for i in range(m - 1):
    ans += comb(cnt[i], k) * (s[i + 1] - s[i]) % mod
    ans %= mod
print(ans)

Solution (Python):
from bisect import bisect_right
from collections import defaultdict
import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
N = 200001
factorialNumInverse = [None] * (N + 1)
naturalNumInverse = [None] * (N + 1)
fact = [None] * (N + 1)

def InverseofNumber(p):
    naturalNumInverse[0] = naturalNumInverse[1] = 1
    for i in range(2, N + 1, 1):
        naturalNumInverse[i] = naturalNumInverse[p % i] * (p - int(p / i)) % p

def InverseofFactorial(p):
    factorialNumInverse[0] = factorialNumInverse[1] = 1
    for i in range(2, N + 1, 1):
        factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % p

def factorial(p):
    fact[0] = 1
    for i in range(1, N + 1):
        fact[i] = fact[i - 1] * i % p

def Binomial(N, R, p):
    ans = fact[N] * factorialNumInverse[R] % p * factorialNumInverse[N - R] % p
    return ans
p = 1000000007
InverseofNumber(p)
InverseofFactorial(p)
factorial(p)
(n, k) = map(int, input().split())
en = defaultdict(lambda : 0)
ex = defaultdict(lambda : 0)
s = set()
for i in range(n):
    (l, r) = map(int, input().split())
    en[l] += 1
    ex[r + 1] += 1
    s.add(l)
    s.add(r + 1)
cnt = 0
ans = 0
last = 0
s = sorted(list(s))
for j in s:
    tot = j - last
    if cnt >= k:
        ans = (ans + Binomial(cnt, k, p) * tot) % p
    cnt += en[j] - ex[j]
    last = j
print(ans)

Solution (Python):
MOD = 10 ** 9 + 7
from sys import stderr

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

def combk(n, k, MOD=MOD, tbl=[]):
    if len(tbl) < k:
        tbl += [0] * k + [1]
    while n >= len(tbl):
        tbl.append(tbl[-1] * len(tbl) * pow(len(tbl) - k, MOD - 2, MOD) % MOD)
    return tbl[n]

def main():
    (n, k) = readints()
    pairs = [readints() for _ in range(n)]
    oplist = [p for (l, r) in pairs for p in (2 * l, 2 * r + 1)]
    oplist.sort()
    count = total = 0
    pos = oplist[0] // 2
    for op in oplist:
        if op & 1:
            (i, delta) = ((op + 1) // 2, -1)
        else:
            (i, delta) = (op // 2, 1)
        total = (total + combk(count, k) * (i - pos)) % MOD
        pos = i
        count += delta
    print(total)
main()