Problem:


Score : 700 points

Problem Statement

Snuke has decided to play a game, where the player runs a railway company.
There are M+1 stations on Snuke Line, numbered 0 through M.
A train on Snuke Line stops at station 0 and every d-th station thereafter, where d is a predetermined constant for each train.
For example, if d = 3, the train stops at station 0, 3, 6, 9, and so forth.

There are N kinds of souvenirs sold in areas around Snuke Line. The i-th kind of souvenirs can be purchased when the train stops at one of the following stations: stations l_i, l_i+1, l_i+2, ..., r_i.

There are M values of d, the interval between two stops, for trains on Snuke Line: 1, 2, 3, ..., M.
For each of these M values, find the number of the kinds of souvenirs that can be purchased if one takes a train with that value of d at station 0.
Here, assume that it is not allowed to change trains.

Constraints

1 ≦ N ≦ 3 × 10^{5}

1 ≦ M ≦ 10^{5}

1 ≦ l_i ≦ r_i ≦ M

Input

The input is given from Standard Input in the following format:

N M
l_1 r_1
:
l_{N} r_{N}

Output

Print the answer in M lines. The i-th line should contain the maximum number of the kinds of souvenirs that can be purchased if one takes a train stopping every i-th station.

Sample Input 1

3 3
1 2
2 3
3 3

Sample Output 1

3
2
2

If one takes a train stopping every station, three kinds of souvenirs can be purchased: kind 1, 2 and 3.

If one takes a train stopping every second station, two kinds of souvenirs can be purchased: kind 1 and 2.

If one takes a train stopping every third station, two kinds of souvenirs can be purchased: kind 2 and 3.

Sample Input 2

7 9
1 7
5 9
5 7
5 9
1 1
6 8
3 4

Sample Output 2

7
6
6
5
4
5
5
3
2



Sample input:
3 3
1 2
2 3
3 3


Sample output:
3
2
2

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate

class Segtree:
    def __init__(self, original, func, element):
        self.n = len(original)
        self.element = element
        self.func = func
        self.N0 = 1 << (self.n-1).bit_length()
        self.seg = [element]*(self.N0 << 1)
        for i, j in enumerate(original, self.N0):
            self.seg[i] = j
        for i in range(self.N0-1, 0, -1):
            self.seg[i] = func(self.seg[2*i], self.seg[2*i+1])

    def get(self, i):
        return self.seg[i+self.N0]
        
    def update(self, i, x):
        i += self.N0
        self.seg[i] = x
        while i > 1:
            y = self.seg[i ^ 1]
            i >>= 1
            x = self.func(x, y)
            self.seg[i] = x
                
    def add(self, i, d):
        self.update(i, self.get(i)+d)
        
    def query(self, l, r):
        l += self.N0
        r += self.N0
        nl = self.element
        nr = self.element
        while l < r:
            if l & 1:
                nl = self.func(nl, self.seg[l])
                l += 1
            if r & 1:
                nr = self.func(nr, self.seg[r-1])
            l >>= 1
            r >>= 1
     
        return self.func(nl, nr)

def main():
  n, m = map(int, input().split())
  LR = [list(map(int, input().split())) for _ in range(n)]
  A = [0]*(m+2)
  for l, r in LR:
    A[l] += 1
    A[r+1] -= 1
  L = Segtree(A, lambda x, y:x+y, 0)
  S = sorted([(r-l+1, l, r) for l, r in LR])
  cnt = 0
  A = []
  for i in range(m, 0, -1):
    while S and S[-1][0] == i:
      c, l, r = S.pop()
      cnt += 1
      L.add(l, -1)
      L.add(r+1, 1)
    res = cnt
    for j in range(0, m+1, i):
      res += L.query(0, j+1)
    A.append(res)
  print(*A[::-1], sep="\n")

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
class Segtree:
    def __init__(self, original, func, element):
        self.n = len(original)
        self.element = element
        self.func = func
        self.N0 = 1 << (self.n-1).bit_length()
        self.seg = [element]*(self.N0 << 1)
        for i, j in enumerate(original, self.N0):
            self.seg[i] = j
        for i in range(self.N0-1, 0, -1):
            self.seg[i] = func(self.seg[2*i], self.seg[2*i+1])

    def get(self, i):
        return self.seg[i+self.N0]
        
    def update(self, i, x):
        i += self.N0
        self.seg[i] = x
        while i > 1:
            y = self.seg[i ^ 1]
            i >>= 1
            x = self.func(x, y)
            self.seg[i] = x
                
    def add(self, i, d):
        self.update(i, self.get(i)+d)
        
    def query(self, l, r):
        l += self.N0
        r += self.N0
        nl = self.element
        nr = self.element
        while l < r:
            if l & 1:
                nl = self.func(nl, self.seg[l])
                l += 1
            if r & 1:
                nr = self.func(nr, self.seg[r-1])
            l >>= 1
            r >>= 1
     
        return self.func(nl, nr)

n, m = map(int, input().split())
L = Segtree([0]*(m+2), lambda x, y:x+y, 0)
LR = [list(map(int, input().split())) for _ in range(n)]
for l, r in LR:
  L.add(l, 1)
  L.add(r+1, -1)
S = sorted([(r-l+1, l, r) for l, r in LR])
cnt = 0
A = []
for i in range(m, 0, -1):
  while S and S[-1][0] == i:
    c, l, r = S.pop()
    cnt += 1
    L.add(l, -1)
    L.add(r+1, 1)
  res = cnt
  for j in range(0, m+1, i):
    res += L.query(0, j+1)
  A.append(res)
print(*A[::-1], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

n, m = map(int, input().split())
L = [0]*(m+2)
for i in range(n):
  l, r = map(int, input().split())
  L[l] += 1<<i
  L[r+1] -= 1<<i
A = list(accumulate(L))
for i in range(1, m+1):
  cnt = 0
  for j in range(0, m+1, i):
    cnt |= A[j]
  print(bin(cnt).count("1"))

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter


class BIT:
    """区間加算、一点取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]

for i in range(n):
    info[i] = info[i][0], info[i][1], info[i][1] - info[i][0] + 1
info = sorted(info, key=itemgetter(2))

bit = BIT(m + 1)
l_info = 0
ans = n
for d in range(1, m + 1):
    while True:
        if l_info < n and info[l_info][2] < d:
            l, r, _ = info[l_info]
            bit.add(l, r + 1, 1)
            l_info += 1
            ans -= 1
        else:
            break
    cnt = ans
    if d == 1:
        print(n)
        continue
    for i in range(0, m + 1, d):
        cnt += bit.get_val(i)
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter


class BIT:
    """区間加算、一点取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]

for i in range(n):
    info[i] = info[i][0], info[i][1], info[i][1] - info[i][0] + 1
info = sorted(info, key=itemgetter(2))

bit = BIT(m + 1)
l_info = 0
ans = n
for d in range(1, m + 1):
    while True:
        if l_info < n and info[l_info][2] < d:
            l, r, _ = info[l_info]
            bit.add(l, r + 1, 1)
            l_info += 1
            ans -= 1
        else:
            break
    cnt = ans
    for i in range(0, m + 1, d):
        cnt += bit.get_val(i)
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

# 内部で1-indexedに変えるので入力は0-indexedでよい
# i項目までの和（i含む）
class BitSum:
    def __init__(self, n):
        self.n = n + 3
        self.table = [0] * (self.n + 1)

    def add(self, i, x):
        i += 1
        while i <= self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

def main():
    n,m=MI()
    dlr=[]
    for _ in range(n):
        l,r=MI()
        dlr.append((r-l+1,l,r+1))
    dlr.sort()
    ans=[0]*(m+1)
    bit=BitSum(m+1)
    i=0
    for k in range(1,m+1):
        while i<n and dlr[i][0]<=k:
            d,l,r=dlr[i]
            bit.add(l,1)
            bit.add(r,-1)
            i+=1
        ans[k]=n-i+sum(bit.sum(a) for a in range(k,m+1,k))
    print(*ans[1:],sep="\n")

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline

#区間[L,R]に1を加えていく
def seg_tree_update(L,R):
    L,R=2**m-1+L,2**m-1+R
    while L<R:
        if L%2==0:
            tree[L]+=1
        if R%2==1:
            tree[R]+=1
        L//=2
        R=R//2-1
    if L==R:
        tree[L]+=1

#数直線xでの和を求める
def seg_tree_sumarize(x):
    ind=2**m-1+x
    SUM=0
    while ind>=0:
        SUM+=tree[ind]
        ind=(ind-1)//2
    return SUM

N,M=map(int,input().split())

data=[]

for i in range(N):
    l,r=map(int,input().split())
    data.append([r-l, l, r])

data.sort()

m=0
while pow(2,m)<M+1:
    m+=1
tree=[0]*(pow(2,m+1)-1)

i=0
for d in range(1,M+1):
    
    #間隔の長さがd以下の区間だけ考えれば良い。
    while i<N and data[i][0]<d:
        seg_tree_update(data[i][1],data[i][2])
        i+=1
    
    ans=0
    
    for j in range((M+1)//d+1):
        if d*j>M:
            break
        ans+=seg_tree_sumarize(d*j)
    
    print(ans+N-i)

Submission status: Time Limit Exceeded

Solution code:
#区間[L,R]に1を加えていく
def seg_tree_update(L,R):
    L,R=2**m-1+L,2**m-1+R
    while L<R:
        if L%2==0:
            tree[L]+=1
        if R%2==1:
            tree[R]+=1
        L//=2
        R=R//2-1
    if L==R:
        tree[L]+=1

#数直線xでの和を求める
def seg_tree_sumarize(x):
    ind=2**m-1+x
    SUM=tree[ind]
    ind=(ind-1)//2
    while ind>=0:
        SUM+=tree[ind]
        ind=(ind-1)//2
    return SUM

N,M=map(int,input().split())

data=[]

for i in range(N):
    l,r=map(int,input().split())
    data.append([r-l, l, r])

data.sort()

m=0
while pow(2,m)<M+1:
    m+=1
tree=[0]*(pow(2,m+1)-1)

i=0
for d in range(1,M+1):
    
    #間隔の長さがd以下の区間だけ考えれば良い。
    while i<N and data[i][0]<d:
        seg_tree_update(data[i][1],data[i][2])
        i+=1
    
    ans=0
    
    for j in range((M+1)//d+1):
        if d*j>M:
            break
        ans+=seg_tree_sumarize(d*j)
    
    print(ans+N-i)

Submission status: Time Limit Exceeded

Solution code:

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret


#区間更新BIT(BITを2つ用意し、BITの長さをN+2で初期化しておくべし)
def bitaddR(l,r,w,bit1,bit2): #半開区間[l,r)にwを加える

    bitadd(l,-1*w*l,bit1)
    bitadd(r,w*r,bit1)
    bitadd(l,w,bit2)
    bitadd(r,-1*w,bit2)

def bitsumR(r,bit1,bit2): #半開区間[1,r)の区間和

    return bitsum(r,bit1) + r * bitsum(r,bit2)


N,M = map(int,input().split())

bitA = [0] * (M+2)
bitB = [0] * (M+2)

len_LR = []

for i in range(N):

    l,r = map(int,input().split())
    len_LR.append([r-l,l,r])

len_LR.sort()
len_LR.append([float("inf"),0,float("inf")])
ind = 0
ns = N
ans = []

for d in range(M):

    d += 1

    while len_LR[ind][2]-len_LR[ind][1]+1 < d:

        bitaddR(len_LR[ind][1] , len_LR[ind][2]+1 , 1 ,bitA,bitB)
        ns -= 1
        ind += 1

    np = 0

    for i in range(d,M+1,d):
        np += bitsumR(i+1,bitA,bitB) - bitsumR(i,bitA,bitB)

    ans.append(ns + np)

print ("\n".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret


#区間更新BIT(BITを2つ用意し、BITの長さをN+2で初期化しておくべし)
def bitaddR(l,r,w,bit1,bit2): #半開区間[l,r)にwを加える

    bitadd(l,-1*w*l,bit1)
    bitadd(r,w*r,bit1)
    bitadd(l,w,bit2)
    bitadd(r,-1*w,bit2)

def bitsumR(r,bit1,bit2): #半開区間[1,r)の区間和

    return bitsum(r,bit1) + r * bitsum(r,bit2)


N,M = map(int,input().split())

bitA = [0] * (M+2)
bitB = [0] * (M+2)

len_LR = []

for i in range(N):

    l,r = map(int,input().split())
    len_LR.append([r-l,l,r])

len_LR.sort()
len_LR.append([float("inf"),0,float("inf")])
ind = 0
ns = N

for d in range(M):

    d += 1

    while len_LR[ind][2]-len_LR[ind][1]+1 < d:

        bitaddR(len_LR[ind][1] , len_LR[ind][2]+1 , 1 ,bitA,bitB)
        ns -= 1
        ind += 1

    np = 0

    for i in range(d,M+1,d):
        np += bitsumR(i+1,bitA,bitB) - bitsumR(i,bitA,bitB)

    print (ns + np)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def solve():
    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def addValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            data[iB] += A
            iB += iB & -iB
    def getSum(iA):
        iB = iA + 1
        ans = 0
        while iB > 0:
            ans += data[iB]
            iB -= iB & -iB
        return ans

    N, M = map(int, input().split())
    querys = []
    for _ in range(N):
        L, R = map(int, input().split())
        querys.append((L, R, 0))
    for d in range(1, M+1):
        for k in range(1, M//d+1):
            querys.append((k*d, M, d, +1))
            querys.append((k*d, k*d-1, d, -1))
            querys.append(((k-1)*d, M, d, -1))
            querys.append(((k-1)*d, k*d-1, d, +1))

    querys.sort()

    data, numPow2 = makeBIT(M+1)

    anss = [0] * (M+1)
    for query in querys:
        _, y, *vs = query
        if vs[0] == 0:
            addValue(y, 1)
        else:
            d, s = vs
            v = getSum(y)
            anss[d] += s*v

    print('\n'.join(map(str, anss[1:])))


solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def solve():
    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def addValue(iA, A):
        iB = iA + 1
        while iB > 0:
            data[iB] += A
            iB -= iB & -iB
    def getValue(iA):
        iB = iA + 1
        ans = 0
        while iB <= numPow2:
            ans += data[iB]
            iB += iB & -iB
        return ans
    def addRangeValue(iFr, iTo, A):
        addValue(iTo, A)
        if iFr > 0:
            addValue(iFr-1, -A)

    N, M = map(int, input().split())
    LRss = [[] for _ in range(M+1)]
    for _ in range(N):
        L, R = map(int, input().split())
        LRss[R-L+1].append((L, R))

    data, numPow2 = makeBIT(M+1)

    anss = []
    numOK = N
    for d in range(1, M+1):
        ans = numOK
        for i in range(d, M+1, d):
            ans += getValue(i)
        anss.append(ans)
        numOK -= len(LRss[d])
        for L, R in LRss[d]:
            addRangeValue(L, R, 1)

    print('\n'.join(map(str, anss)))


solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict

N,M = map(int,input().split())
d_to_L = [[] for _ in range(M+1)]
for _ in range(N):
    L,R = map(int,input().split())
    d_to_L[R-L+1].append(L)

tree = [0] * (M+1) # BIT で管理。左にあるLの個数 - (R+1)の個数 → いくつの[L,R]に入っているか
long = N # 長すぎて自動回収できる
answer = [0] * (M+1)

for m in range(1,M+1):
    for L in d_to_L[m]:
        x = L
        while x <= M:
            tree[x] += 1
            x += x & (-x)
        x = L+m
        while x <= M:
            tree[x] -= 1
            x += x & (-x)
        long -= 1
    s = long
    for x in range(m,M+1,m):
        while x:
            s += tree[x]
            x -= x & (-x)
    answer[m] = s

print('\n'.join(map(str, answer[1:])))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def Sum(self, i):#1からiまでの和
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def PointAdd(self, i, x):#
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

	def SegAdd(self, l, r, x):#lからrにxを足す
		self.PointAdd(l, x)
		self.PointAdd(r+1, -x)
		return

n, m = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(n)]
s.sort(key=lambda x: x[1]-x[0])
b = BIT(m)

too_long = n #r-l+1よりも大きい区間（必ず訪れる）
cur = 0
for i in range(1, m+1):
	while cur < n and s[cur][1]-s[cur][0]+1 < i:
		too_long -= 1
		b.SegAdd(s[cur][0], s[cur][1], 1)
		cur += 1
	ans = too_long
	for j in range(i, m+1, i):
		ans += b.Sum(j)
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict

N,M = map(int,input().split())
d_to_LR = defaultdict(list)
for _ in range(N):
    L,R = map(int,input().split())
    d_to_LR[R-L+1].append((L,R))

tree = [0] * (M+1) # BIT で管理。左にあるLの個数 - (R+1)の個数 → いくつの[L,R]に入っているか
long = N # 長すぎて自動回収できる
answer = [0] * (M+1)

for m in range(1,M+1):
    for L,R in d_to_LR[m]:
        x = L
        while x <= M:
            tree[x] += 1
            x += x & (-x)
        x = R+1
        while x <= M:
            tree[x] -= 1
            x += x & (-x)
        long -= 1
    s = long
    for x in range(m,M+1,m):
        while x:
            s += tree[x]
            x -= x & (-x)
    answer[m] = s

print('\n'.join(map(str, answer[1:])))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict

N,M = map(int,input().split())
d_to_LR = defaultdict(list)
for _ in range(N):
    L,R = map(int,input().split())
    d_to_LR[R-L+1].append((L,R))

def BIT_update(tree,x,value):
    while x <= M:
        tree[x] += value
        x += x & (-x)

def BIT_sum(tree,x):
    s = 0
    while x:
        s += tree[x]
        x -= x & (-x)
    return s

tree = [0] * (M+1) # BIT で管理。左にあるLの個数 - (R+1)の個数 → いくつの[L,R]に入っているか
long = N # 長すぎて自動回収できる
answer = [0] * (M+1)

for m in range(1,M+1):
    for L,R in d_to_LR[m]:
        BIT_update(tree,L,1)
        BIT_update(tree,R+1,-1)
        long -= 1
    answer[m] = sum(BIT_sum(tree,x) for x in range(m,M+1,m)) + long

print('\n'.join(map(str, answer[1:])))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
#import matplotlib.pyplot as plt
#import numpy as np

from bisect import bisect
from operator import itemgetter
def inpl(): return list(map(int, input().split()))


class BIT:
    def __init__(self, N):
        self.size = 2 ** (int.bit_length(N)+1)
        self.tree = [0]*(self.size + 1)

    def sum(self, i):
        res = 0
        while i:
            res += self.tree[i]
            i -= (i & -(i))
        return res

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self.tree[i] += x
            i += (i & -(i))


class RABIT():
    # range add BIT
    def __init__(self, N):
        self.bit0 = BIT(N)
        self.bit1 = BIT(N)

    def sum(self, i):
        return i*self.bit1.sum(i) + self.bit0.sum(i)

    def add_range(self, l, r, x):
        self.bit0.add(l, -x*(l-1))
        self.bit1.add(l, x)
        self.bit0.add(r+1, x*r)
        self.bit1.add(r+1, -x)

    def get_range(self, l, r):
        return self.sum(r) - self.sum(l-1)


N, M = inpl()
R, L, S = [], [], []
Q = []
for _ in range(N):
    l, r = inpl()
    Q.append((l, r, (r-l+1)))

Q = sorted(Q, key=itemgetter(2), reverse=True)
rabit = RABIT(M+1)

Lmin = M
Rmax = 0
for i in range(1, M+1):
    while Q and Q[-1][2] < i:
        l, r, _ = Q.pop()
        rabit.add_range(l, r, 1)
        Lmin = min(Lmin, l)
        Rmax = max(Rmax, r)
    ans = len(Q)
    for j in range(-(-Lmin//i) * i, Rmax+1, i):
        ans += rabit.get_range(j, j)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect
from operator import itemgetter
inpl = lambda: list(map(int, input().split()))


class BIT:
    def __init__(self, N):
        self.size = 2 ** (int.bit_length(N)+1)
        self.tree = [0]*(self.size + 1)

    def sum(self, i):
        res = 0
        while i:
            res += self.tree[i]
            i -= (i & -(i))
        return res

    def add(self, i, x):
        while 1 <= i <= self.size:
            self.tree[i] += x
            i += (i & -(i))


class RABIT():
    # range add BIT
    def __init__(self, N):
        self.bit0 = BIT(N)
        self.bit1 = BIT(N)

    def sum(self, i):
        return i*self.bit1.sum(i) + self.bit0.sum(i)

    def add_range(self, l, r, x):
        self.bit0.add(l, -x*(l-1))
        self.bit1.add(l, x)
        self.bit0.add(r+1, x*r)
        self.bit1.add(r+1, -x)

    def get_range(self, l, r):
        return self.sum(r) - self.sum(l-1)


N, M = inpl()
R, L, S = [], [], []
Q = []
for _ in range(N):
    l, r = inpl()
    Q.append((l, r, (r-l+1)))

Q = sorted(Q, key=itemgetter(2), reverse=True)
rabit = RABIT(M+1)

for i in range(1, M+1):
    while Q and Q[-1][2] < i:
        l, r, _ = Q.pop()
        rabit.add_range(l, r, 1)
    ans = len(Q)
    for j in range(i, M+1, i):
        ans += rabit.get_range(j, j)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import itertools

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
class RangeUpdate:
    def __init__(self, n):
        self.p = Bit(n + 1)
        self.q = Bit(n + 1)
     
    def add(self, s, t, x):
        t += 1
        self.p.add(s, -x * s)
        self.p.add(t, x * t)
        self.q.add(s, x)
        self.q.add(t, -x)
     
    def sum(self, s, t):
        t += 1
        return self.p.sum(t) + self.q.sum(t) * t - \
               self.p.sum(s) - self.q.sum(s) * s

n,m = [int(i) for i in input().split()]
lr = [[int(i) for i in input().split()] for _ in range(n)]

lr.sort(key=lambda x: x[1]-x[0])

#print(lr)

omiyage = RangeUpdate(m+1)
index = 0
for d in range(1,m+1):
    while(index < n and lr[index][1] - lr[index][0] < d):
        omiyage.add(lr[index][0]+1, lr[index][1]+1, 1)
        index+=1
    ans = 0
    pos = 0
    while(pos <= m):
        ans += omiyage.sum(pos+1,pos+1)
        pos += d
    ans += n-index
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, k, x):
        while k <= self.n:
            self.bit[k] += x
            k += k & -k

    def sum(self, k):
        s = 0
        while k > 0:
            s += self.bit[k]
            k -= k & -k
        return s


n, m = map(int, input().split())
st = BIT(m)
L, R = [], []
d = [[] for i in range(m + 1)]
for i in range(n):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
    d[r - l + 1].append(i)

num = n
for i in range(1, m + 1):
    num -= len(d[i])
    for j in d[i]:
        st.add(L[j], 1)
        st.add(R[j] + 1, -1)

    tmp = 0
    k = i
    for j in range(k, m + 1, i):
        tmp += st.sum(j)

    print(num + tmp)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sumi(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N, M = inpl()
H = defaultdict(lambda: [])
for _ in range(N):
    l, r = inpl()
    H[r-l+1].append(l)
Q = BIT(M+1)
ctr = N
for i in range(1,M+1):
    ctr -= len(H[i]) 
    for j in H[i]:
        Q.add(j, 1)
        Q.add(j+i, -1)
    ans = 0
    for k in range(i,M+1,i):
        ans += Q.sumi(k)
    print(ctr + ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
L = []
for i in range(N):
    l, r = map(int, input().split())
    L.append((r-l+1, l, r+1))
L.sort()


class Bit:
    """
    0-indexed
    # 使用例
    bit = Bit(10)  # 要素数
    bit.add(2, 10)
    print(bit.sum(5))  # 10
    """
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)

    def sum(self, i):
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


class BitImos:
    """
    ・範囲すべての要素に加算
    ・ひとつの値を取得
    の2種類のクエリをO(logn)で処理
    """
    def __init__(self, n):
        self.bit = Bit(n+1)

    def add(self, s, t, x):
        # [s, t)にxを加算
        self.bit.add(s, x)
        self.bit.add(t, -x)

    def get(self, i):
        return self[i]

    def __getitem__(self, key):
        # 位置iの値を取得
        return self.bit.sum(key+1)


imos = BitImos(M+1)
il = 0
a = N
A = [0]*M
for i in range(1, M+1):
    while il<N:
        ra, l, r = L[il]
        if i < ra:
            break
        il+=1
        a-=1
        imos.add(l, r, 1)
    ans = 0
    for j in range(i, M+1, i):
        ans += imos[j]

    A[i-1] = ans + a

print(*A, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
L = []
for i in range(N):
    l, r = map(int, input().split())
    L.append((r-l+1, l, r+1))
L.sort()


class Bit:
    """
    0-indexed
    # 使用例
    bit = Bit(10)  # 要素数
    bit.add(2, 10)
    print(bit.sum(5))  # 10
    """
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)

    def sum(self, i):
        # [0, i) の要素の総和を返す
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


class BitImos:
    """
    ・範囲すべての要素に加算
    ・ひとつの値を取得
    の2種類のクエリをO(logn)で処理
    """
    def __init__(self, n):
        self.bit = Bit(n+1)

    def add(self, s, t, x):
        # [s, t)にxを加算
        self.bit.add(s, x)
        self.bit.add(t, -x)

    def get(self, i):
        return self[i]

    def __getitem__(self, key):
        # 位置iの値を取得
        return self.bit.sum(key+1)


imos = BitImos(M+1)
il = 0
a = N
A = [0]*M
for i in range(1, M+1):
    while il<N:
        ra, l, r = L[il]
        if i < ra:
            break
        il+=1
        a-=1
        imos.add(l, r, 1)
    ans = 0
    for j in range(i, M+1, i):
        ans += imos[j]

    A[i-1] = ans + a

print(*A, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
L = []
for i in range(N):
    l, r = map(int, input().split())
    L.append((r-l+1, l, r+1))
L.sort()


class Bit:
    """
    0-indexed
    # 使用例
    bit = Bit(10)  # 要素数
    bit.add(2, 10)
    print(bit.sum(5))  # 10
    """
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)

    def sum(self, i):
        # [0, i) の要素の総和を返す
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


class BitImos:
    """
    ・範囲すべての要素に加算
    ・ひとつの値を取得
    の2種類のクエリをO(logn)で処理
    """
    def __init__(self, n):
        self.bit = Bit(n+1)

    def add(self, s, t, x):
        # [s, t)にxを加算
        self.bit.add(s, x)
        self.bit.add(t, -x)

    def get(self, i):
        return self[i]

    def __getitem__(self, key):
        # 位置iの値を取得
        return self.bit.sum(key+1)


imos = BitImos(M+1)
il = 0
a = N
for i in range(1, M+1):
    while il<N:
        ra, l, r = L[il]
        if i < ra:
            break
        il+=1
        a-=1
        imos.add(l, r, 1)
    ans = 0
    for j in range(i, M+1, i):
        ans += imos[j]

    print(ans + a)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
L = []
for i in range(N):
    l, r = map(int, input().split())
    L.append((r-l+1, l, r+1))
L.sort()


class Bit:
    """
    0-indexed
    # 使用例
    bit = Bit(10)  # 要素数
    bit.add(2, 10)
    print(bit.sum(5))  # 10
    """
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  # O(nlogn)
        return str(list(self))

    def sum(self, i):
        # [0, i) の要素の総和を返す
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        # 足し算と引き算にはaddを使うべき
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])

class BitImos:
    """
    ・範囲すべての要素に加算
    ・ひとつの値を取得
    の2種類のクエリをO(logn)で処理
    """
    def __init__(self, n):
        self.bit = Bit(n+1)

    def add(self, s, t, x):
        # [s, t)にxを加算
        self.bit.add(s, x)
        self.bit.add(t, -x)

    def get(self, i):
        return self[i]

    def __getitem__(self, key):
        # 位置iの値を取得
        return self.bit.sum(key+1)


imos = BitImos(M+1)
il = 0
a = N
for i in range(1, M+1):
    while il<N:
        ra, l, r = L[il]
        if i < ra:
            break
        il+=1
        a-=1
        imos.add(l, r, 1)
    ans = 0
    for j in range(i, M+1, i):
        ans += imos[j]

    print(ans + a)