AtCoder Beginner Contest 221 D

https://atcoder.jp/contests/abc221/tasks/abc221_d

分割統治法で、区間の集まりを[(first, last, num)]で表して、それをマージする、というコードを書いたら意外と長いコードになってしまって、max1462msec。
解説を見ると、ああって感じで、書いてみたら実質8行。でも、1216msecであまり変わりませんでした。最初に書いたコードは、考え方は汎用性があると思います。

以下は、PyPy2のコードです。

# coding: utf-8
# Online games

from collections import Counter


#################### library ####################

def read_int():
    return int(raw_input())

def read_tuple():
    return tuple(map(int, raw_input().split()))

def read_list():
    return list(map(int, raw_input().split()))

def digits(n):
    while n:
        n, d = divmod(n, 10)
        yield d


#################### naive ####################

def F_naive(intervals):
    c = Counter()
    first = min(A for A, B in intervals)
    last = max(A+B for A, B in intervals)
    for d in range(first, last):
        n = sum(1 for A, B in intervals if A <= d < A+B)
        c[n] += 1
    return [ c[n] for n in range(1, len(intervals) + 1) ]


#################### process ####################

def read_input():
    N = read_int()
    intervals = [ read_tuple() for _ in range(N) ]
    return intervals

import random
def random_intervals(first, last):
    A = random.randrange(first, last)
    B = random.randrange(1, last - first)
    return (A, B)

def F(intervals):
    def g(ints):
        if len(ints) == 1:
            A, B = ints[0]
            yield (A, A+B, 1)
            return
        
        mid = len(ints) / 2
        ints1 = list(g(ints[:mid]))
        ints2 = list(g(ints[mid:]))
        k, l = 0, 0
        while k < len(ints1) and l < len(ints2):
            A1, B1, n1 = ints1[k]
            A2, B2, n2 = ints2[l]
            if B1 == B2:
                if A1 == A2:
                    yield (A1, B1, n1+n2)
                elif A1 < A2:
                    yield (A1, A2, n1)
                    yield (A2, B1, n1+n2)
                else:
                    yield (A2, A1, n2)
                    yield (A1, B1, n1+n2)
                k += 1
                l += 1
            elif B1 < B2:
                if B1 <= A2:
                    yield ints1[k]
                elif A1 == A2:
                    yield (A1, B1, n1+n2)
                    ints2[l] = (B1, B2, n2)
                elif A1 < A2:
                    yield (A1, A2, n1)
                    yield (A2, B1, n1+n2)
                    ints2[l] = (B1, B2, n2)
                else:
                    yield (A2, A1, n2)
                    yield (A1, B1, n1+n2)
                    ints2[l] = (B1, B2, n2)
                k += 1
            else:
                if B2 <= A1:
                    yield ints2[l]
                elif A1 == A2:
                    yield (A1, B2, n1+n2)
                    ints1[k] = (B2, B1, n1)
                elif A1 < A2:
                    yield (A1, A2, n1)
                    yield (A2, B2, n1+n2)
                    ints1[k] = (B2, B1, n1)
                else:
                    yield (A2, A1, n2)
                    yield (A1, B2, n1+n2)
                    ints1[k] = (B2, B1, n1)
                l += 1
        
        for int1 in ints1[k:]:
            yield int1
        
        for int2 in ints2[l:]:
            yield int2
    
    c = Counter()
    for first, last, n in g(intervals):
        c[n] += last - first
    return [ c[n] for n in range(1, len(intervals) + 1) ]


#################### main ####################

intervals = read_input()
#intervals = [ random_intervals(1, 100) for _ in range(3) ]
#print F_naive(intervals)
v = F(intervals)
print ' '.join(map(str, v))