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

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()
    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
        print(n-i+sum(bit.sum(a) for a in range(k,m+1,k)))

main()

Submission status: Accepted

Solution code:
"""
BIT
区間[L,R]にxを加える。
座標Xでの値を求める。
"""
import sys
input=sys.stdin.readline

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

def bit_sum(i):
    s=0
    while i>0:
        s+=tree[i]
        i-=i&(-i)
    return s

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()

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

Submission status: Accepted

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(x,bit): #ind 1～aまでの和を求める
   
    ret = 0
    while x:
        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())

BIT = [0] * (M+1)
dic = {}
for i in range(N):
    l,r = map(int,input().split())
    if r-l+1 not in dic:
        dic[r-l+1] = []
    dic[r-l+1].append([l,r])

ind = 0
ns = N
ans = []
for d in range(M):

    d += 1

    if d in dic:
        for L,R in dic[d]:

            bitadd(L , 1 ,BIT)
            bitadd(R+1 , -1 , BIT)
            ns -= 1

    nm = 0
    for i in range(d,M+1,d):
        
        nm += bitsum(i,BIT)
    ans.append(nm+ns)

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

Submission status: Accepted

Solution code:
# instead of AVLTree
class BITbisect():
    def __init__(self, max):
        self.max = max
        self.data = [0]*(self.max+1)
    
    # 0からiまでの区間和
    # 立っているビットを下から処理
    def query_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # i番目の要素にxを足す
    # 覆ってる区間すべてに足す
    def add(self, i, x):
        while i <= self.max:
            self.data[i] += x
            i += i & -i

    def insert(self, x):
        self.add(x, 1)

    def delete(self, x):
        self.add(x, -1)

    def count(self, x):
        return self.query_sum(x) - self.query_sum(x-1)
    
    def length(self):
        return self.query_sum(self.max)
    
    # 下からc番目(0-indexed)の数
    # O(log(N))
    def search(self, c):
        c += 1
        s = 0
        ind = 0
        l = self.max.bit_length()
        for i in reversed(range(l)):
            if ind + (1<<i) <= self.max:
                if s + self.data[ind+(1<<i)] < c:
                    s += self.data[ind+(1<<i)]
                    ind += (1<<i)
        if ind == self.max:
            return False
        return ind + 1
    
    def bisect_right(self, x):
        return self.query_sum(x)

    def bisect_left(self, x):
        if x == 1:
            return 0
        return self.query_sum(x-1)

    # listみたいに表示
    def display(self):
        print('inside BIT:', end=' ')
        for x in range(1, self.max+1):
            if self.count(x):
                c = self.count(x)
                for _ in range(c):
                    print(x, end=' ')
        print()

import sys
input = sys.stdin.readline

base = 10**9

N, M = map(int, input().split())
Pairs = [[] for _ in range(M+1)]
for _ in range(N):
    a, b = map(int, input().split())
    Pairs[b-a+1].append(a*base+b)

ansbit = BITbisect(M+1)
usingbit = BITbisect(M+1)

for length, inPairs in enumerate(Pairs):
    if length==0: continue

    ansbit.add(1, len(inPairs))
    ansbit.add(length+1, -len(inPairs))

    rem = M//length
    c = 0
    for r in range(1, rem+1):
        c += usingbit.query_sum(r*length)
    ansbit.add(length, c)
    ansbit.add(length+1, -c)

    for p in inPairs:
        l = p//base
        r = p%base
        usingbit.add(l, 1)
        usingbit.add(r+1, -1)
    
for n in range(1, M+1):
    print(ansbit.query_sum(n))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
NN = (M + 10).bit_length()
BIT=[0]*(2**NN+1)

def addrange(l0, r0, x=1):
    l, r = l0, r0
    while l <= 2**NN:
        BIT[l] += x
        l += l & (-l)
    while r <= 2**NN:
        BIT[r] -= x
        r += r & (-r)
def getvalue(r):
    a = 0
    while r != 0:
        a += BIT[r]
        r -= r&(-r)
    return a

X = []
for _ in range(N):
    l, r = map(int, input().split())
    X.append((l, r+1))

X = sorted(X, key = lambda x: -(x[1]-x[0]))
for d in range(1, M+1):
    while X and X[-1][1] - X[-1][0] < d:
        l, r = X.pop()
        addrange(l, r)
    ans = len(X)
    for i in range(d, M+1, d):
        ans += getvalue(i)
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))


class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0 for _ in range(n+1)]
        self.p = 2**(n.bit_length() - 1)
        self.dep = n.bit_length()

    def get(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

    def bl(self, v):
        if v <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < v:
                s += k
                v -= self.tree[s+k]
            k //= 2
        return s + 1


def main():
  n, m = map(int, input().split())
  lr = [tuple(map(int, input().split())) for _ in range(n)]
  bt = BIT(m)

  lr = list(sorted(lr, key=lambda x: x[1]-x[0]))
  i = 0
  for d in range(1, m+1):
    for i in range(i, n):
      if lr[i][1]-lr[i][0]+1==d:
        bt.add(lr[i][0], 1)
        bt.add(lr[i][1]+1, -1)
        if i == n-1:
          i = n
          break
      else:
        break

    ans = n - i
    for j in range(d, m+1, d):
      ans += bt.get(j)
    print(ans)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def main():
  n, m = map(int, input().split())
  lr = [tuple(map(int, input().split())) for _ in range(n)]
  BIT = [0 for _ in range(m+1)]

  def bit_add(a, w):
    x = a
    while x <= m:
      BIT[x] += w
      x += x&-x

  def bit_sum(a):
    ret = 0
    x = a
    while x > 0:
      ret += BIT[x]
      x -= x&-x
    return ret

  lr = list(sorted(lr, key=lambda x: x[1]-x[0]))
  i = 1
  for d in range(1, m+1):
    while i<=n and lr[i-1][1]-lr[i-1][0]+1==d:
      bit_add(lr[i-1][0], 1)
      bit_add(lr[i-1][1]+1, -1)
      i += 1
    ans = n - i + 1
    for j in range(d, m+1, d):
      ans += bit_sum(j)
    print(ans)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from bisect import bisect
from operator import itemgetter

import sys
input = sys.stdin.readline

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

Solution code:
import sys
input = sys.stdin.readline
class BIT():
    def __init__(self, number):
        self.n = number
        self.list = [0] * (number + 1)

    def add(self, i, x):  # ith added x  1indexed
        while i <= self.n:
            self.list[i] += x
            i += i & -i

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

    def suma(self, i, j):  # i,i+1,..j sum
        return self.search(j) - self.search(i - 1)

N,M=map(int,input().split())
L=[[] for i in range(M+1)]
bit=BIT(M+1)
for i in range(N):
    l,r=map(int,input().split())
    L[r-l+1].append((l,r))
ans=N
for i in range(1,M+1):
    num=0
    for l,r in L[i]:
        ans-=1
        bit.add(l,1)
        bit.add(r+1,-1)
    num+=ans
    for j in range(i,M+1,i):
        num+=bit.search(j)
    print(num)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline #文字列入力のときは注意

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.base = [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):
        self.base[i] += x
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
    def get(self, i):
        return self.base[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

#    def get(self, s):
#        return self.p.sum(s+1) + self.q.sum(s+1) * (s+1) - \
#               self.p.sum(s) - self.q.sum(s) * s
    def get(self, s):
        return self.p.get(s+1) + self.q.get(s+1) * (s+1) + self.q.sum(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.get(pos+1)
        pos += d
    ans += n-index
    print(ans)

Submission status: Accepted

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

def add(B,a,s):
    x=a
    while x<=len(B)-1:
        B[x]+=s
        x+=x&(-x)
        
def sums(B,a):
    x=a
    S=0
    while x!=0:
        S+=B[x]
        x-=x&(-x)
    return S

Line=[0]*(M+2)
K=N
for d in range(1,M+1):
  for l,r in section[d]:
    add(Line,l,1)
    add(Line,r+1,-1)
    K-=1
  ans=K
  for s in range(M//d+1):
    ans+=sums(Line,s*d)
  print(ans)

Submission status: Accepted

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

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

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

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

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
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: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
section = [list(map(int, input().split())) for i in range(N)]

# 区間の大きさごとに分類
D = defaultdict(list)
for sec in section:
    D[sec[1] - sec[0] + 1].append(sec)


class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 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 reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(M)

for d in range(1, M + 1):
    for l, r in D[d - 1]:
        N -= 1
        BIT.add(l, 1)
        BIT.add(r + 1, -1)

    ans = N
    for i in range(d, M + 1, d):
        ans += BIT.sum(i)
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
section = [list(map(int, input().split())) for i in range(N)]

# 区間の大きさごとに分類
D = defaultdict(list)
for sec in section:
    D[sec[1] - sec[0] + 1].append(sec)


class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 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 reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(M)
certainly = 0  # 確実に通るもの

for d in range(1, M + 1):
    for l, r in D[d - 1]:
        certainly += 1
        BIT.add(l, 1)
        BIT.add(r + 1, -1)

    ans = N - certainly
    for i in range(d, M + 1, d):
        ans += BIT.sum(i)
    print(ans)

Submission status: Accepted

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

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:
        ans += bit.sum(cur)
        cur += d

    print(ans)

Submission status: Accepted

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, ri + 1, ri - li + 1))

    sects.sort(key=itemgetter(2))

    print(N)

    left = 0
    ft = FenwickTree(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

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

        print(ans)


class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.data = [0]*(size + 1)

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

    def get_sum(self, r):
        res = 0

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

        return res

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

    def sum(self,idx):
        ret=0
        while idx>0:
            ret+=self.node[idx]
            idx-=idx&(-idx)
        return ret

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

n,m=map(int,raw_input().split())
L=[[] for _ in xrange(m+1)]
for i in xrange(n):
    l,r=map(int,raw_input().split())
    r+=1
    L[r-l].append(l)
bit=BIT(m+1)
total=0
for d in xrange(1,m+1):
    for l in L[d]:
        r=l+d
        bit.add(l,1)
        bit.add(r,-1)
    total+=len(L[d])
    ans=n-total
    now=0
    while now<=m:
        ans+=bit.sum(now)
        now+=d
    print(ans)

Submission status: Accepted

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

    def sum(self,idx):
        ret=0
        while idx>0:
            ret+=self.node[idx]
            idx-=idx&(-idx)
        return ret

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

n,m=map(int,raw_input().split())
L=[[] for _ in xrange(m+1)]
for i in xrange(n):
    l,r=map(int,raw_input().split())
    r+=1
    L[r-l].append(l)
bit=BIT(m+1)
ans=n
total=0
for d in xrange(1,m+1):
    for l in L[d]:
        r=l+d
        bit.add(l,1)
        bit.add(r,-1)
    total+=len(L[d])
    ans=n-total
    now=0
    while now<=m:
        ans+=bit.sum(now)
        now+=d
    print(ans)

Submission status: Runtime Error

Solution code:
x = int(input())

ans = x // 11 * 2
print(ans + (x % 11 > 0) + (x % 11 > 6))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
NN = (M + 10).bit_length() - 1
BIT=[0]*(2**NN+1)

def addrange(l0, r0, x=1):
    l, r = l0, r0
    while l <= 2**NN:
        BIT[l] += x
        l += l & (-l)
    while r <= 2**NN:
        BIT[r] -= x
        r += r & (-r)
def getvalue(r):
    a = 0
    while r != 0:
        a += BIT[r]
        r -= r&(-r)
    return a

X = []
for _ in range(N):
    l, r = map(int, input().split())
    X.append((l, r+1))

X = sorted(X, key = lambda x: -(x[1]-x[0]))
for d in range(1, M+1):
    while X and X[-1][1] - X[-1][0] < d:
        l, r = X.pop()
        addrange(l, r)
    ans = len(X)
    for i in range(d, M+1, d):
        ans += getvalue(i)
    print(ans)

Submission status: Runtime Error

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_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]:
        R = L+m-1
        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: Runtime Error

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


class BIT:
    from math import log2

    def __init__(self, N):
        self.size = 2 ** (-int(-log2(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: Runtime Error

Solution code:
def is_prime(N):
    if N < 2:
        return False
    i = 2
    while i*i <= N:
        if N % i == 0:
            return False
        i += 1
    return True


def main():
    N = int(input())
    if not is_prime(N):
        dsum = 0
        for c in str(N):
            dsum += int(c)
        if N == 1 or N % 10 in [2, 4, 5, 6, 8, 0] or dsum % 3 == 0:
            print("Not Prime")
            return
    print("Prime")


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def add(B,a,s):
    x=a
    while x<=len(B):
        B[x]+=s
        x+=x&(-x)
        
def sums(B,a):
    x=a
    S=0
    while x!=0:
        S+=B[x]
        x-=x&(-x)
    return S

Line=[0]*(M+2)
K=N
for d in range(1,M+1):
  for l,r in section[d]:
    add(Line,l,1)
    add(Line,r+1,-1)
    K-=1
  ans=K
  for s in range(M//d+1):
    ans+=sums(Line,s*d)
  print(ans)

Submission status: Runtime Error

Solution code:
from math import sqrt
N, M = map(int, input().split())
D = [0]*(M+2); R = [0]*(M)
for i in range(N):
    l, r = map(int, input().split())
    D[1] += 1
    D[r+1] -= 1
    if l <= r-l+1:
        continue
    D[r-l+2] -= 1
    D[l] += 1

    left = r-l+2; right = l
    for k in range(2, int(sqrt(r))+1):
        l0 = max((l+k-1) // k, left); r0 = min((r // k + 1, right))
        if l0 < r0:
            D[l0] += 1
            D[r0] -= 1
        right = l0

print(*R, *D)
tmp = 0
for i in range(1, M+1):
    tmp += D[i]
    R[i-1] += tmp
print(*R, sep='\n')