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:
# seishin.py
N, M = map(int, input().split())
D = [[] for i in range(M+1)]
for i in range(N):
    l, r = map(int, input().split())
    D[r-l+1].append(l)

data = [0]*(M+2)
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def add(k, x):
    while k <= M+1:
        data[k] += x
        k += k & -k

C = N
ans = []
for d in range(1, M+1):
    for l in D[d]:
        add(l, 1)
        add(l+d, -1)
        C -= 1

    cnt = C
    i = d
    while i <= M:
        cnt += get(i)
        i += d
    ans.append(cnt)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools
import heapq
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_I(): return map(int, stdin)
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))



##### main #####

class BIT(object):

	def __init__(self,l):
		self.size = l
		self.bit = [0]* (self.size+1)

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

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

	def __str__(self):
		return str(self.bit)


def main():
	N,M = LI()

	bit = BIT(M+2)
	L = []
	R = []
	b = [[] for i in range(M+1)]


	for i in range(N):
		l,r = LI()
		L.append(l); R.append(r)
		b[r-l +1].append(i)


	gone = 0
	for d in range(1, M+1):
		for i in b[d]:
			gone+=1
			bit.add(L[i], 1)
			bit.add(R[i]+1, -1)


		ans = N-gone

		for m in range(d, M+1, d):

			ans += bit.sum(m)
		print(ans)




if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class BIT():
    def __init__(self, n):
        i = 1
        while 2**i <= n:
            i += 1
        self.H = i
        self.N = 2**i
        self.A = [0] * self.N

    def find(self, i):
        r = 0
        while i:
            r += self.A[i]
            i -= i & (i-1) ^ i
        return r

    def update(self, i, x):
        while i < self.N:
            self.A[i] += x
            i += i & (i-1) ^ i

    def query(self, a, b):
        return self.find(b-1) - self.find(a-1)

def main():
    n,m = LI()
    d = collections.defaultdict(list)
    for _ in range(n):
        l,r = LI()
        d[r-l+1].append((l,r))
    r = [n]
    bit = BIT(m+3)
    c = n
    for i in range(2,m+1):
        for a,b in d[i-1]:
            c -= 1
            bit.update(a,1)
            bit.update(b+1,-1)
        t = c
        for j in range(i,m+1,i):
            t += bit.find(j)
        r.append(t)

    return '\n'.join(map(str,r))


print(main())

Submission status: Time Limit Exceeded

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

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

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

    def __str__(self):
        return str(self.bit)

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

bit = BIT(m + 1)
t = 0
for d in range(1, m + 1):
    for l in lr[d]:
        #print(l, l + d)
        bit.add(l, 1)
        #print(bit.bit)
        bit.add(l + d, -1)
        #print(bit.bit)

    t += len(lr[d])
    ans = n - t

    cur = 0
    while cur <= m:
        # bitの0 ~ curまでの総和を加算
        ans += bit.sum(cur)
        cur += d

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def snuke_line_2():
	n, m = map(int, raw_input().split(" "))
	souvenirs = []
	for i in range(n):
		souvenirs.append(map(int, raw_input().split(" ")))
	# print souvenirs
	stations = list(range(m+1))
	for d in range(1, m+1):
		passed_stations = stations[::d]
		s_count = 0
		for s_interval in souvenirs:
			tag = False
			if s_interval[1]-s_interval[0]>d:
				tag = True
			else:
				for s in passed_stations:
					if s>=s_interval[0] and s<=s_interval[1]:
						tag = True
						break
			if tag:
				s_count+=1
		print s_count


if __name__ == "__main__":
	snuke_line_2()

Submission status: Time Limit Exceeded

Solution code:
def snuke_line():
	n, m = map(int, raw_input().split(" "))
	souvenirs = []
	for i in range(n):
		souvenirs.append(map(int, raw_input().split(" ")))
	# print souvenirs
	stations = list(range(m+1))
	for d in range(1, m+1):
		passed_stations = stations[::d]
		s_count = 0
		for s_interval in souvenirs:
			tag = False
			for s in passed_stations:
				if s>=s_interval[0] and s<=s_interval[1]:
					tag = True
					break
			if tag:
				s_count+=1
		print s_count


if __name__ == "__main__":
	snuke_line()

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter

mod = 10**9 + 7
inf = 1<<30

def solve():
    N, M = map(int, sys.stdin.readline().split())
    sects = []

    for i in range(N):
        li, ri = map(int, sys.stdin.readline().split())

        sects.append((li - 1, ri, ri - li + 1))

    sects.sort(key=itemgetter(2))

    # print(sects)

    print(N)

    left = 0

    ft = FenwickTree([0]*(M + 1))

    for d in range(2, M + 1):
        for j in range(left, N):
            if sects[j][2] >= d:
                left = j
                break
            else:
                ft.add(sects[j][0], 1)
                ft.add(sects[j][1], -1)
        else:
            left = N

        # print('left', left)
        # print(ft.data)

        ans = N - left + sum(ft.get_sum(j) for j in range(d, M + 1, d))
        
        print(ans)

class FenwickTree:
    def __init__(self, a):
        self.n = len(a)
        self.data = [0] + a[:]

        for i in range(1, self.n + 1):
            if i + (i & (-i)) <= self.n:
                self.data[i + (i & (-i))] += self.data[i]

    def add(self, i, x):
        ''' a[i] += x '''
        i += 1 # 0-oringn -> 1-origin

        while i <= self.n:
            self.data[i] += x
            i += i & (-i)

    def get_sum(self, r):
        ''' sum[a_0 .. a_r) '''
        res = 0

        while r > 0:
            res += self.data[r]
            r -= r & (-r)

        return res


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

num_N, num_M = map(int, input().split())
l_item = [list(map(int, input().split())) for __ in range(num_N)]

l_all = [[] for __ in range(num_M + 1)]

for index, item in enumerate(l_item):
    for i in range(item[0], item[1] + 1):
        l_all[i].append(index)

for d in range(1, num_M + 1):
    count = 0
    ans = 0
    l_counter = []

    while True:
        count += 1
        num_sta = d * count
        if num_sta > num_M:
            break

        if len(l_all[num_sta]) != 0:
            for i in l_all[num_sta]:
                if i in l_counter:
                    continue
                else:
                    l_counter.append(i)
                    ans += 1

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split(" "))
l = [0 for i in range(N)]
r = [0 for i in range(N)]
for i in range(N):
    l[i], r[i] = map(int, input().split(" "))

res = [0 for i in range(M)]

for i in range(N):
    for j in range(M):
        if l[i]%(j+1) ==0 and l[i]//(j+1) == r[i]//(j+1):
            res[j] += 1
        elif l[i]//(j+1) != r[i]//(j+1):
            res[j] += 1

for i in range(M):
    print(res[i])

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split(" ")))

mat = []
for i in range(M):
    mat.append([])

for i in range(N):
    l, r = list(map(int, input().split(" ")))
    
    for j in range(l, r+1):
        mat[j-1].append(i)

mat.insert(0, [])

def flatten(nested_list):
    """2重のリストをフラットにする関数"""
    return [e for inner_list in nested_list for e in inner_list]

for d in range(1,M+1):
    print (len(set(flatten(mat[::d]))))

Submission status: Time Limit Exceeded

Solution code:
#coding: UTF-8
import time
start_time=time.clock()
N,M=map(int,input().split())
d_list=[[0]]*M
sd_list=[0]*M
for i in range(0,N):
    l,r=map(int,input().split())
    d=r-l
    for j in range(0,d+1):
        sd_list[j]+=1
    if d_list[d]==[0]:
        d_list[d]=[[l,r]]
    else:
        d_list[d].append([l,r])

plist=[[0 for i in range(0,M)] for i in range(0,M)]
for i in range(0,M):
    if 0 not in d_list[i]:
        for L in d_list[i]:
            for j in range(L[0],L[1]+1):
                plist[i][j-1]+=1

out=[0]*M
out[0]=sd_list[0]
for i in range(1,M):
    out[i]=sd_list[i]
    for k in range(0,i):
        for j in range(i,M,i+1):
            out[i]+=plist[k][j]

for i in range(0,M):
    print(out[i])

Submission status: Time Limit Exceeded

Solution code:
[n,m]=[int(i) for i in input().split()]
l=[]
r=[]
for i in range(n):
  [a,b]=[int(i) for i in input().split()]
  l.append(a)
  r.append(b)
c=0
for i in range(1,m+1):
  for j in range(n):
    if int(r[j]/i)-int(l[j]/i)>0 or r[j]%i==0 or l[j]%i==0:
        c+=1
  print(c)
  c=0

Submission status: Time Limit Exceeded

Solution code:
#coding: UTF-8
N,M=map(int,input().split())
out={}
for i in range(1,N+1):
    l,r=map(int,input().split())
    for j in range(0,M):
        if r//(j+1)-l//(j+1)>=1 or r%(j+1)==0 or l%(j+1)==0:
            if j in out:
                out[j]+=1
            else:
                out[j]=1
for i in range(0,M):
    print(out[i])

Submission status: Time Limit Exceeded

Solution code:
#coding: UTF-8
N,M=map(int,input().split())
out=[0]*M
for i in range(1,N+1):
    l,r=map(int,input().split())
    for j in range(0,M):
        if r//(j+1)-l//(j+1)>=1 or r%(j+1)==0 or l%(j+1)==0:
            out[j]+=1
for i in range(0,M):
    print(out[i])

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,raw_input().split(" "))
items=[]
for _ in xrange(0,N):
    items.append(map(int,raw_input().split(" ")))

for d in xrange(1,M+1):
    isget=[False]*N
    for k in range(0,M+1,d):
        for i,item in enumerate(items):
            isget[i]=item[0]<=k<=item[1] or isget[i]
    print sum(isget)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,raw_input().split(" "))
items=[]
for _ in range(0,N):
    items.append(map(int,raw_input().split(" ")))

for d in range(1,M+1):
    isget=[False]*N
    for k in range(0,M+1,d):
        for i,item in enumerate(items):
            isget[i]=item[0]<=k<=item[1] or isget[i]
    print sum(isget)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
res = [0] * m
for t in range(n):
  l, r = map(int, input().split())
  res = [res[i-1] + (l <= r//i*i) for i in range(1, m+1)]
for v in res:
  print(v)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
lr = []
for i in range(n):
    l, r = map(int, input().split())
    lr.append([l, r])

meisan_kinds = [0 for i in range(m + 1)]
for i in range(n):
    l, r = lr[i]
    j = 1
    while True:
        if j <= r - l + 1:
            meisan_kinds[j] += 1
        elif j < l:
            if l // j != r // j or l % j == 0:
                meisan_kinds[j] += 1
        elif l <= j and j <= r:
            meisan_kinds[j] += 1
        else:
            break
        j += 1

for i in range(1, m + 1):
    print(meisan_kinds[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG: {} -> {}'.format(name, val), file=sys.stderr)
            return None

N, M = map(int, input().split())
L = {}
R = {}

for i in range(N):
    left, right = map(int, input().split())
    if left in L:
        L[left].add(i)
    else:
        L[left] = {i}

    if (right + 1) in R:
        R[right + 1].add(i)
    else:
        R[right + 1] = {i}

# debug(L, locals())
# debug(R, locals())

eki_kaeru = [set()] * (M + 1)
tmp = set()

for eki in range(M + 1):
    if eki in L:
        eki_kaeru[eki] = tmp.union(L[eki])
    else:
        eki_kaeru[eki] = tmp.copy()
    if eki in R:
        eki_kaeru[eki] -= R[eki]

    tmp = eki_kaeru[eki]
    # debug(tmp, locals())

# debug(eki_kaeru, locals())

ans = []

for d in range(1, M + 1):
    buy = set()

    for i in range(0, M + 1, d):
        buy = buy.union(eki_kaeru[i])

    ans.append(len(buy))

print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())

d = [0] * (M + 1)

for i in range(N):
    l, r = map(int, input().split())
    for m in range(1, M + 1):
        if (l % m == 0 or m - (l % m) <= r - l):
            d[m] += 1

print(*d[1:], sep='\n')

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
lr = []
for i in range(n):
    l, r = map(int, input().split())
    lr.append([l, r])

meisan_kinds = []
for i in range(1, m + 1):
    c = 0
    for j in range(n):
        l, r = lr[j]
        if l // i != r // i or l % i == 0:
            c += 1
    meisan_kinds.append(c)

for i in range(len(meisan_kinds)):
    print(meisan_kinds[i])

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    n,m = LI()
    d = [LI() for _ in range(n)]
    a = [1] * (10001)
    t = [set([1]),set([1])]
    for i in range(2,10001):
        if a[i] == 1:
            t.append(set([1,i]))
        else:
            ti = t[a[i]]
            c = i//a[i]
            ti = ti | set(c*_ for _ in ti)
            t.append(ti)
        ai = i*2
        while ai <= 10000:
            a[ai] = i
            ai += i

    e = [0] * 10001
    for l,r in d:
        if l*2 < r:
            for i in range(1,r+1):
                e[i] += 1
            continue
        s = t[r]
        for i in range(l,r):
            s = s | t[i]
        for c in s:
            e[c] += 1
    for i in range(1,m+1):
        print(e[i])


main()

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


m = {}
tm = {}
def ff(n):
    if n <= 1:
        return set([1])
    if n in m:
        return m[n]
    fa = factorization(n)
    t = ff(n//fa[0][0])
    t |= set([fa[0][0] * _ for _ in t])
    m[n] = t
    return t

def main():
    n,m = LI()
    d = [LI() for _ in range(n)]
    a = [1] * (10001)
    t = [set([1]),set([1])]
    for i in range(2,10001):
        if a[i] == 1:
            t.append(set([1,i]))
        else:
            ti = t[a[i]]
            c = i//a[i]
            ti = ti | set(c*_ for _ in ti)
            t.append(ti)
        ai = i*2
        while ai <= 10000:
            a[ai] = i
            ai += i

    e = [0] * 10001
    for l,r in d:
        s = t[r]
        for i in range(l,r):
            s = s | t[i]
        for c in s:
            e[c] += 1
    for i in range(1,m+1):
        print(e[i])


main()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
data = [list(map(int, input().split())) for i in range(n)]
for i in range(1, m+1):
  res = sum(map(lambda x: (x[0]-1)//i + 1 <= x[1]//i, data))
  print(res)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], i8), cache=True)
def get_sum(bit, i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


@njit((i8[:], i8, i8), cache=True)
def add(bit, i, x):
    while i < len(bit):
        bit[i] += x
        i += i & -i

@njit((i8, i8[:]), cache=True)
def main(M, LR):
    L, R = LR[::2], LR[1::2]
    R = R + 1
    D = R - L
    argsort = np.argsort(D)
    L, R, D = L[argsort], R[argsort], D[argsort]
    idx = np.searchsorted(D, np.arange(M + 2))

    bit = np.zeros(M + 10, np.int64)
    rest = len(L)
    for d in range(1, M + 1):
        # 長さ d の区間を追加
        for i in range(idx[d], idx[d + 1]):
            rest -= 1
            add(bit, L[i], 1)
            add(bit, R[i], -1)
        ans = rest
        for n in range(d, M + 1, d):
            ans += get_sum(bit, n)
        print(ans)

N, M = map(int, readline().split())
LR = np.array(read().split(), np.int64)

main(M, LR)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,m = map(int,readline().split())
lr = list(map(int,read().split()))

imos = [0] * (m+2)
ans = [0] * (m+2)

it = iter(lr)
for l,r in zip(it,it):
    i = 1
    li = r+1
    while(li > i):
        ri = min(li, r//i + 1)
        li = (l-1)//i + 1
        if(ri > li):
            imos[li] += 1
            imos[ri] -= 1
        i+=1

    for i in range(1,li):
        if(r//i)-((l-1)//i)>0:
            ans[i] += 1

for i in range(1,m+1):
    imos[i] += imos[i-1]
    ans[i] += imos[i]

print('\n'.join(map(str,ans[1:m+1])))

Submission status: Accepted

Solution code:
class BIT: #0-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length()
        self.n0 = 1<<self.depth
#        self.element = [0]*(n+1)
    def get_sum(self, i): #a_0 + ... + a_{i} #閉区間
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def query(self,l,r): #a_l + ... + a_r 閉区間
        return self.get_sum(r) - self.get_sum(l-1) 
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        # self.element[i] += x
    #def get(self,i): return element[i]        
    def bisect_left(self,w):
        #和が w 以上になる最小の index
        #w が存在しない場合 self.size を返す
        if w <= 0: return 0
        x,k = 0,self.n0
        for _ in range(self.depth):
            k >>= 1
            if x+k <= self.size and self.tree[x+k] < w:
                w -= self.tree[x+k]
                x += k
        return x
    

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,m,*lr = map(int,read().split())

mp = iter(lr)
dlr = [(r-l+1,l,r) for l,r in zip(mp,mp)]
dlr.sort(reverse=True)

ans = [0]*(m+1)

b = BIT(m+2)

for i in range(1,m+1):
    while dlr and dlr[-1][0] < i:
        d,l,r = dlr.pop()
        b.add(l,1)
        b.add(r+1,-1)
        #print(i,l,r)
    
    v = 0
    for j in range(i,m+1,i):
        v += b.get_sum(j)
    #print(b.get_sum(1),b.get_sum(2),b.get_sum(3), b.get_sum(4))   
            
    ans[i] = len(dlr) + v

print(*ans[1:],sep="\n")

Submission status: Accepted

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

    def query(self,idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        while idx <= self.num:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

import sys

input=sys.stdin.readline

N,M=map(int,input().split())
q={i:[] for i in range(1,M+1)}
imos=[0 for i in range(M+2)]
for i in range(N):
    l,r=map(int,input().split())
    q[l].append(r)
    imos[l]+=1
    imos[r+1]-=1
for i in range(1,M+1):
    imos[i]+=imos[i-1]
res={i:imos[i*(M//i)] for i in range(1,M+1)}

query={i:[] for i in range(1,M+1)}
for i in range(1,M+1):
    for j in range(1,M//i):
        query[i*j].append(i*j+i)

bit=BIT(M)
for i in range(1,M+1):
    for r in q[i]:
        bit.update(r,1)
    for r in query[i]:
        res[r-i]+=bit.query(r-1)-bit.query(i-1)

for i in range(1,M+1):
    print(res[i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = []
for i in range(N):
  l, r = map(int, input().split())
  a.append((l, r))
a.sort(key = lambda x: x[0] - x[1])
#print(a)
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j = None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
  def lowerbound(self, s):
    x = 0
    y = 0
    for i in range(self.n.bit_length(), -1, -1):
      k = x + (1 << i)
      if k <= self.n and (y + self.data[k] < s):
        y += self.data[k]
        x += 1 << i
    return x + 1
fwk = BIT(M + 1)
for l in range(1, M + 1):
  res = len(a)
  for x in range(l, M + 1, l): res += fwk.sum(x)
  while len(a):
    if a[-1][1] - a[-1][0] <= l:
      fwk.add(a[-1][0], 1)
      fwk.add(a.pop()[1] + 1, -1)
    else: break
  print(res)

Submission status: Accepted

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

def main():
  n, m = map(int, input().split())
  S = [[] for _ in range(m+1)]
  for _ in range(n):
    l, r = map(int, input().split())
    S[r-l+1].append((l, r))
  
  BIT = [0]*(m+2)
  def add(i, a):
    while i <= m+1:
      BIT[i] += a
      i += i&(-i)
  def bit_sum(i):
    res = 0
    while i > 0:
      res += BIT[i]
      i -= i&(-i)
    return res
  cnt = n
  for i in range(1, m+1):
    for l, r in S[i]:
      cnt -= 1
      add(l, 1)
      add(r+1, -1)
    res = cnt
    for j in range(0, m+1, i):
      res += bit_sum(j)
    print(res)

if __name__ == "__main__":
  main()

Submission status: Accepted

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

def main():
  n, m = map(int, input().split())
  LR = [list(map(int, input().split())) for _ in range(n)]
  
  BIT = [0]*(m+2)
  def add(i, a):
    while i <= m+1:
      BIT[i] += a
      i += i&(-i)
  def bit_sum(i):
    res = 0
    while i > 0:
      res += BIT[i]
      i -= i&(-i)
    return res
  
  S = sorted([(r-l+1, l, r) for l, r in LR], reverse=True)
  cnt = n
  L = []
  for i in range(1, m+1):
    while S and S[-1][0] == i:
      c, l, r = S.pop()
      cnt -= 1
      add(l, 1)
      add(r+1, -1)
    res = cnt
    for j in range(0, m+1, i):
      res += bit_sum(j)
    L.append(res)
  print(*L, sep="\n")

if __name__ == "__main__":
  main()

Submission status: Accepted

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

def main():
  n, m = map(int, input().split())
  LR = [list(map(int, input().split())) for _ in range(n)]
  
  BIT = [0]*(m+2)
  def add(i, a):
    while i <= m+1:
      BIT[i] += a
      i += i&(-i)
  def bit_sum(i):
    res = 0
    while i > 0:
      res += BIT[i]
      i -= i&(-i)
    return res
  
  for l, r in LR:
    add(l, 1)
    add(r+1, -1)
  
  S = sorted([(r-l+1, l, r) for l, r in LR])
  cnt = 0
  L = []
  for i in range(m, 0, -1):
    while S and S[-1][0] == i:
      c, l, r = S.pop()
      cnt += 1
      add(l, -1)
      add(r+1, 1)
    res = cnt
    for j in range(0, m+1, i):
      res += bit_sum(j)
    L.append(res)
  print(*L[::-1], sep="\n")

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from operator import itemgetter
import sys
input = sys.stdin.buffer.readline


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
res = [0] * m
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)
    res[d - 1] = cnt

print('\n'.join(map(str, res)), end='\n')

Submission status: Accepted

Solution code:
from operator import itemgetter
import sys
input = sys.stdin.readline


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
res = [0] * m
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)
    res[d - 1] = cnt

print('\n'.join(map(str, res)), end='\n')

Submission status: Accepted

Solution code:
from operator import itemgetter
import sys
input = sys.stdin.readline


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: Accepted

Solution code:
from operator import itemgetter
import sys
input = sys.stdin.readline


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)