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: Wrong Answer

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//i
        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: Wrong Answer

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+1)//i)
        li = l//i
        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: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	m, n = tin()
	imos = [0]*(n+2)
	for _ in range(m):
		l, r = tin()
		dist = r - l
		min_r=r
		if 1+dist+1 < l:
			imos[1]+=1
			imos[1+dist+1] +=-1
			imos[l]+=1
			imos[r+1]-=1
			for i in range(1, int(r**0.5)+1+dist):
				#pa(imos)
				if r % i <= dist:
					#pa(('i',i))
					rr = (r // i)
					if rr <= i:
						break
					if 1+dist+1 <= i and i < l:
						imos[i]+=1
						imos[i+1]-=1
					if 1+dist+1 <= rr and rr < l:
						#pa(rr)
						imos[rr]+=1
						imos[rr+1]-=1
		else:
			#pa('hhh')
			imos[1]+=1
			imos[r+1]+=-1
		#pa(imos)
	
	ret=0
	for v in imos[1:-1]:
		ret += v
		print( ret)
		
def main_onm():
	#O(nm)
	m, n = tin()
	imos = [0]*(n+1)
	for _ in range(m):
		l, r = tin()
		dist = r - l
		for i in range(1, min(n, r)+1):
			if r % i <= dist:
				imos[i]+=1

	ret=0
	#print(imos)
	for v in imos[1:]:
		#ret += v
		print(v)

def main2():
	k, n = tin()
	imos = [0]*(n+1)
	#b , c = tin()
	#s = input()
	for _ in range(k):
		l, r = tin()
		dist = r - l
		imos[0]+=1
		pre = dist+1
		pa(('dist:',dist))
		for i in range(2, int(r**0.5)+1):
			if r % i <= dist:
				pa(('i:',i))
				if pre > i - dist:
					pass
				else:
					imos[pre]-=1
					imos[(i-1) - dist]+=1
				pre = r
		else:
			if pre > r - dist:
				pass
			else:
				imos[pre]-=1
				imos[(r-1) - dist]+=1
			pre = r
			imos[pre] -= 1
					
	ret=0
	print(imos)
	for v in imos:
		ret += v
		print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	m, n = tin()
	imos = [0]*(n+2)
	for _ in range(m):
		l, r = tin()
		dist = r - l
		min_r=r
		if 1+dist+1 < l:
			imos[1]+=1
			imos[1+dist+1] +=-1
			imos[l]+=1
			imos[r+1]-=1
			for i in range(1, r+1): #int(r**0.5)+1+dist):
				#pa(imos)
				if r % i <= dist:
					#pa(('i',i))
					if 1+dist+1 <= i and i < l:
						imos[i]+=1
						imos[i+1]-=1
					rr=(r//i)
					if rr <= i:
						break
					if 1+dist+1 <= rr and rr < l:
						#pa(rr)
						imos[rr]+=1
						imos[rr+1]-=1
		else:
			#pa('hhh')
			imos[1]+=1
			imos[r+1]+=-1
		#pa(imos)
	
	ret=0
	for v in imos[1:-1]:
		ret += v
		print(ret)
		
def main_onm():
	#O(nm)
	m, n = tin()
	imos = [0]*(n+1)
	for _ in range(m):
		l, r = tin()
		dist = r - l
		for i in range(1, min(n, r)+1):
			if r % i <= dist:
				imos[i]+=1

	ret=0
	#print(imos)
	for v in imos[1:]:
		#ret += v
		print(v)

def main2():
	k, n = tin()
	imos = [0]*(n+1)
	#b , c = tin()
	#s = input()
	for _ in range(k):
		l, r = tin()
		dist = r - l
		imos[0]+=1
		pre = dist+1
		pa(('dist:',dist))
		for i in range(2, int(r**0.5)+1):
			if r % i <= dist:
				pa(('i:',i))
				if pre > i - dist:
					pass
				else:
					imos[pre]-=1
					imos[(i-1) - dist]+=1
				pre = r
		else:
			if pre > r - dist:
				pass
			else:
				imos[pre]-=1
				imos[(r-1) - dist]+=1
			pre = r
			imos[pre] -= 1
					
	ret=0
	print(imos)
	for v in imos:
		ret += v
		print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	m, n = tin()
	imos = [0]*(n+2)
	for _ in range(m):
		l, r = tin()
		dist = r - l
		min_r=r
		if 1+dist+1 < l:
			imos[1]+=1
			imos[1+dist+1] +=-1
			imos[l]+=1
			imos[r+1]-=1
			for i in range(1, int(r**0.5)+1+dist):
				#pa(imos)
				if r % i <= dist:
					#pa(('i',i))
					if 1+dist+1 <= i and i < l:
						imos[i]+=1
						imos[i+1]-=1
					rr=(r//i)
					if rr <= i:
						break
					if 1+dist+1 <= rr and rr < l:
						#pa(rr)
						imos[rr]+=1
						imos[rr+1]-=1
		else:
			#pa('hhh')
			imos[1]+=1
			imos[r+1]+=-1
		#pa(imos)
	
	ret=0
	for v in imos[1:-1]:
		ret += v
		print(ret)
		
def main_onm():
	#O(nm)
	m, n = tin()
	imos = [0]*(n+1)
	for _ in range(m):
		l, r = tin()
		dist = r - l
		for i in range(1, min(n, r)+1):
			if r % i <= dist:
				imos[i]+=1

	ret=0
	#print(imos)
	for v in imos[1:]:
		#ret += v
		print(v)

def main2():
	k, n = tin()
	imos = [0]*(n+1)
	#b , c = tin()
	#s = input()
	for _ in range(k):
		l, r = tin()
		dist = r - l
		imos[0]+=1
		pre = dist+1
		pa(('dist:',dist))
		for i in range(2, int(r**0.5)+1):
			if r % i <= dist:
				pa(('i:',i))
				if pre > i - dist:
					pass
				else:
					imos[pre]-=1
					imos[(i-1) - dist]+=1
				pre = r
		else:
			if pre > r - dist:
				pass
			else:
				imos[pre]-=1
				imos[(r-1) - dist]+=1
			pre = r
			imos[pre] -= 1
					
	ret=0
	print(imos)
	for v in imos:
		ret += v
		print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	m, n = tin()
	imos = [0]*(n+2)
	for _ in range(m):
		l, r = tin()
		dist = r - l
		min_r=r
		if 1+dist+1 < l:
			imos[1]+=1
			imos[1+dist+1] +=-1
			imos[l]+=1
			imos[r+1]-=1
			for i in range(1, int(r**0.5)+1+2):
				#pa(imos)
				if r % i <= dist:
					#pa(('i',i))
					if 1+dist < i and i < l:
						imos[i]+=1
						imos[i+1]-=1
					rr=(r//i)
					if rr <= i:
						break
					if 1+dist < rr and rr < l:
						#pa(rr)
						imos[rr]+=1
						imos[rr+1]-=1
		else:
			#pa('hhh')
			imos[1]+=1
			imos[r+1]+=-1
		#pa(imos)
	
	ret=0
	for v in imos[1:-1]:
		ret += v
		print(ret)
		
def main_onm():
	#O(nm)
	m, n = tin()
	imos = [0]*(n+1)
	for _ in range(m):
		l, r = tin()
		dist = r - l
		for i in range(1, min(n, r)+1):
			if r % i <= dist:
				imos[i]+=1

	ret=0
	#print(imos)
	for v in imos[1:]:
		#ret += v
		print(v)

def main2():
	k, n = tin()
	imos = [0]*(n+1)
	#b , c = tin()
	#s = input()
	for _ in range(k):
		l, r = tin()
		dist = r - l
		imos[0]+=1
		pre = dist+1
		pa(('dist:',dist))
		for i in range(2, int(r**0.5)+1):
			if r % i <= dist:
				pa(('i:',i))
				if pre > i - dist:
					pass
				else:
					imos[pre]-=1
					imos[(i-1) - dist]+=1
				pre = r
		else:
			if pre > r - dist:
				pass
			else:
				imos[pre]-=1
				imos[(r-1) - dist]+=1
			pre = r
			imos[pre] -= 1
					
	ret=0
	print(imos)
	for v in imos:
		ret += v
		print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	m, n = tin()
	imos = [0]*(n+2)
	for _ in range(m):
		l, r = tin()
		dist = r - l
		min_r=r
		if 1+dist+1 < l:
			imos[1]+=1
			imos[1+dist+1] +=-1
			imos[l]+=1
			imos[r+1]-=1
			for i in range(1, int(r**0.5)+1+1):
				#pa(imos)
				if r % i <= dist:
					#pa(('i',i))
					if 1+dist < i and i < l:
						imos[i]+=1
						imos[i+1]-=1
					rr=(r//i)
					if rr <= i:
						break
					if 1+dist < rr and rr < l:
						#pa(rr)
						imos[rr]+=1
						imos[rr+1]-=1
		else:
			#pa('hhh')
			imos[1]+=1
			imos[r+1]+=-1
		pa(imos)
	
	ret=0
	for v in imos[1:-1]:
		ret += v
		print(ret)
		
def main_onm():
	#O(nm)
	m, n = tin()
	imos = [0]*(n+1)
	for _ in range(m):
		l, r = tin()
		dist = r - l
		for i in range(1, min(n, r)+1):
			if r % i <= dist:
				imos[i]+=1

	ret=0
	#print(imos)
	for v in imos[1:]:
		#ret += v
		print(v)

def main2():
	k, n = tin()
	imos = [0]*(n+1)
	#b , c = tin()
	#s = input()
	for _ in range(k):
		l, r = tin()
		dist = r - l
		imos[0]+=1
		pre = dist+1
		pa(('dist:',dist))
		for i in range(2, int(r**0.5)+1):
			if r % i <= dist:
				pa(('i:',i))
				if pre > i - dist:
					pass
				else:
					imos[pre]-=1
					imos[(i-1) - dist]+=1
				pre = r
		else:
			if pre > r - dist:
				pass
			else:
				imos[pre]-=1
				imos[(r-1) - dist]+=1
			pre = r
			imos[pre] -= 1
					
	ret=0
	print(imos)
	for v in imos:
		ret += v
		print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
"""
Mo ?
っぽいので書いてみよう

"""
def Sieve(n): #n以下の素数全列挙(O(nloglogn)) retは素数が入ってる。divlisはその数字の素因数が一つ入ってる

    ret = []
    divlis = [-1] * (n+1) #何で割ったかのリスト(初期値は-1)
    
    flag = [True] * (n+1)
    flag[0] = False
    flag[1] = False

    ind = 2
    while ind <= n:

        if flag[ind]:
            ret.append(ind)

            ind2 = ind ** 2

            while ind2 <= n:
                flag[ind2] = False
                divlis[ind2] = ind
                ind2 += ind

        ind += 1

    return ret,divlis

def rd(n,divlis):

    dic = {}
    cms = []
    ret = [1]

    while divlis[n] != -1:

        if divlis[n] not in dic:
            dic[divlis[n]] = 1
            cms.append(divlis[n])
        else:
            dic[divlis[n]] += 1
        n //= divlis[n]

    if n > 1 and n not in dic:
        dic[n] = 1
        cms.append(n)
    elif n > 1:
        dic[n] += 1

    for i in cms:
        nloop = len(ret)
        
        for j in range(dic[i]):
            j += 1
            
            for k in range(nloop):
                ret.append(ret[k] * (i**j))

    return ret
            
    

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

retlis,divlis = Sieve(M+1)

#print (retdiver(24,divlis))



blr = []

rootN = int(N**0.5)
for i in range(N):

    l,r = map(int,input().split())
    blr.append([l // rootN,l,r])

blr.sort()

dic = {}
l = 0
r = 0

ans = [0] * (M+1)
ans[1] = 1

for lp in range(N):

    ql = blr[lp][1]
    qr = blr[lp][2]

    while r < qr:

        nlis = rd(r+1,divlis)
        for i in nlis:
            if i not in dic:
                dic[i] = 1
            else:
                dic[i] += 1
        r += 1

    while l > ql:

        nlis = rd(l-1,divlis)
        for i in nlis:
            if i not in dic:
                dic[i] = 1
            else:
                dic[i] += 1
        l -= 1   

    while r > qr:

        nlis = rd(r,divlis)
        for i in nlis:
            if i not in dic:
                dic[i] = -1
            else:
                dic[i] -= 1
        r -= 1

    while l < ql:

        nlis = rd(l,divlis)
        for i in nlis:
            if i not in dic:
                dic[i] = -1
            else:
                dic[i] -= 1
        l += 1

    dlis = []
    for i in dic:
        if dic[i] > 0:
            ans[i] += 1
        else:
            dlis.append(i)

    for i in dlis:
        del dic[i]


    #print (l,r,ql,qr)
    #print (dic,nlis)

    
for i in range(M):
    i += 1
    print (ans[i])

Submission status: Wrong Answer

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)

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 + 1) * i, Rmax+1, i):
        ans += rabit.get_range(j, j)
    print(ans)

Submission status: Wrong Answer

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


class Prime:
    def __init__(self, number):  # N以下の素数
        self.jud = [True] * (number + 5)
        self.pri = []
        self.jud[0] = False
        self.jud[1] = False

        for i in range(number):
            if self.jud[i]:
                self.pri.append(i)
                for j in range(2, (number) // i + 1):
                    self.jud[i * j] = False

    def judge(self, x):
        return self.jud[x]

    def decom(self, x):
        s = x
        a = defaultdict(int)
        if s == 1:
            return a
        while s > 1:
            for p in self.pri:
                if s % p == 0:
                    a[p] += 1
                    s = s // p
                    break
        return a


N,M=map(int,input().split())
L=[tuple([int(i) for i in input().split()]) for i in range(N)]
Ki=Prime(M+1)
A=Ki.pri
#print(A)

def f(x):
    num=0
    for l,r in L:
        if l%x==0:
            num+=1
        elif r%x==0:
            num+=1
        elif l//x<r//x:
            num+=1
    return num

dd=defaultdict(int)
for a in A:
    for i in range(32):
        if pow(a,i)>M:
            break
        dd[pow(a,i)] = f(pow(a,i))
#print(dd)
print(dd[1])
for i in range(2,M+1):

    di=Ki.decom(i)
    L=[]
    for p,n in di.items():
        L.append(pow(p,n))
    ans=0
    t=len(L)
    if t==1:
        print(dd[i])
        continue
    for j in range(t<<1):
        num=0
        s=1
        coef=0
        for k in range(t):
            if j & (1<<k):
                s*=L[k]
                coef+=1
        if s==i:
            continue
        ans+=((-1)**(t-coef-1))*dd[s]
        #print(ans,coef,s,dd[s])
    dd[i]=ans
    print(ans)

Submission status: Wrong Answer

Solution code:
#これでTLEしたら草ですねぇ！
class SegTree():
	def __init__(self, size):
		self.size = 1
		while self.size < size:
			self.size *= 2
		self.table = [set() for _ in range(2 * self.size - 1)]

n, m = map(int, input().split())
#m = int(input())
s = SegTree(m+1)
l = s.size
for i in range(1, m+1):
	for j in range(0, m+1, i):
		k = j+l-1
		s.table[k].add(i)
		while k > 0:
			k = (k-1) // 2
			s.table[k].add(i)
#print(s.table)
def query(a, b, k, l, r):
	if r <= a or b <= l:
		return set()
	elif a <= l and r <= b:
		return s.table[k]
	else:
		vl = query(a, b, k*2+1, l, (l+r)//2)
		vr = query(a, b, k*2+2, (l+r)//2, r)
		return vl | vr

for i in range(n):
	x, y = map(int, input().split())
	print(query(x, y+1, 0, 0, l))

Submission status: Wrong Answer

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 r0 <= left:
            break
        if l0 < r0:
            D[l0] += 1; D[r0] -= 1
        right = l0

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N, M = [int(n) for n in input().split()]


souvenir_range = []
for i in range(N):
    l, r = [int(n) for n in input().split()]
    souvenir_range.append(list(range(l, r+1)))
print(souvenir_range)


stop_list_each_train = []
for i in range(1, M+1):
    stop_list_each_train.append(list(set([(i*m) % (M+1) for m in range(M+1) if i*m <= M])))
print(stop_list_each_train)

for stop_list in stop_list_each_train:
    counter = 0
    for souvenir in souvenir_range:
        for stop in stop_list:
            if stop in souvenir:
                counter += 1
                break
    print(counter)

Submission status: Wrong Answer

Solution code:
#coding: UTF-8
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
    if d_list[d]==[0]:
        d_list[d]=[[l,r]]
    else:
        d_list[d].append([l,r])

for i in range(0,M):
    if d_list[i]!=[0]:
        sd_list[i]=len(d_list[i])
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: Wrong Answer

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

    def get(self, i):
        result = 0
        x = i
        while x > 0:
            result += self.a[x]
            x -= x & -x
        return result

    def _add(self, i, v):
        x = i
        while x <= self.n:
            self.a[x] += v
            x += x & -x

    def add(self, l, r, v):
        self._add(l, v)
        self._add(r + 1, -v)


n, m = map(int, input().split())

souvenirs = {i: set() for i in range(1, m + 1)}
for l, r in (map(int, input().split()) for _ in range(n)):
    souvenirs[r - l + 1].add((l, r))

inevitable = n
st = RangeAddTree(m)

print(n)
for l, r in souvenirs[1]:
    st.add(l, r, 1)
inevitable -= len(souvenirs[1])

for i in range(2, m + 1):
    result = inevitable
    t = i
    while t <= m:
        result += st.get(t)
        t += i
    print(result)
    for l, r in souvenirs[i]:
        st.add(l, r, 1)
    inevitable -= len(souvenirs[i])

Submission status: Wrong Answer

Solution code:
from math import ceil, log2


class SegmentTree:
    def __init__(self, n):
        tn = 2 ** ceil(log2(n))
        self.a = [0] * (tn * 2)

    def find(self, c, l, r, i):
        if l == r:
            return self.a[c]
        mid = (l + r) // 2
        if i <= mid:
            return self.a[c] + self.find(c * 2, l, mid, i)
        else:
            return self.a[c] + self.find(c * 2 + 1, mid + 1, r, i)

    def add(self, c, l, r, s, t, x):
        if l == r or l == s and r == t:
            self.a[c] += x
            return
        mid = (l + r) // 2
        if t <= mid:
            self.add(c * 2, l, mid, s, t, x)
        elif s > mid:
            self.add(c * 2 + 1, mid + 1, r, s, t, x)
        else:
            self.add(c * 2, l, mid, s, mid, x)
            self.add(c * 2 + 1, mid + 1, r, mid + 1, t, x)


n, m = map(int, input().split())

souvenirs = {i: set() for i in range(1, m + 1)}
for l, r in (map(int, input().split()) for _ in range(n)):
    souvenirs[r - l + 1].add((l, r))

inevitable = n
st = SegmentTree(m)

print(n)
for l, r in souvenirs[1]:
    st.add(1, 1, m, l, r, 1)
inevitable -= len(souvenirs[1])

for i in range(2, m + 1):
    result = inevitable
    t = i
    while t <= m:
        result += st.find(1, 1, m, t)
        t += i
    print(result)
    for l, r in souvenirs[i]:
        st.add(1, 1, m, l, r, 1)
    inevitable -= len(souvenirs[i])

Submission status: Wrong Answer

Solution code:
#coding: UTF-8
import time
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-l>=(j+1):
            out[j]+=1
        elif 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:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from math import sqrt
    input = sys.stdin.readline

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

    m = int(sqrt(M))
    if m*m > M:
        m -= 1

    imos = [0] * (M+2)
    ans = [0] * (M+1)
    for _ in range(N):
        l, r = map(int, input().split())
        for i in range(1, m+1):
            ll = (l-1) // i + 1
            rr = r // i
            if rr >= ll:
                ans[i] += 1
        imos[l] += 1
        imos[r+1] -= 1
        l_prev = l
        for i in range(2, m+1):
            ll = (l - 1) // i + 1
            rr = r // i
            if rr >= ll:
                if rr < l_prev:
                    imos[ll] += 1
                    imos[rr+1] -= 1
                else:
                    imos[l_prev] -= 1
                    imos[ll] += 1
                l_prev = ll
    ans2 = [0] * (M+1)
    for i in range(1, M+1):
        ans2[i] = ans2[i-1] + imos[i]
    for i in range(1, m+1):
        print(ans[i])
    for i in range(m+1, M+1):
        print(ans2[i])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main3():
	#O(nm)
	m, n = tin()
	imos = [0]*(n+1)
	for _ in range(m):
		l, r = tin()
		dist = r - l
		min_r=r
		for i in range(1, min(n, int(r**0.5)+2)):
			if i >=min_r:
				break
			pa(i)
			if r % i <= dist:
				imos[i]+=1
				rr=(r//i)
				if rr <= n+1:
					imos[rr]+=1
					min_r=rr
		print(imos)
	ret=0
	print(imos)
	for v in imos[1:]:
		#ret += v
		print(v)
		
def main():
	#O(nm)
	m, n = tin()
	imos = [0]*(n+1)
	for _ in range(m):
		l, r = tin()
		dist = r - l
		for i in range(1, min(n, r)+1):
			if r % i <= dist:
				imos[i]+=1

	ret=0
	#print(imos)
	for v in imos[1:]:
		#ret += v
		print(v)

def main2():
	k, n = tin()
	imos = [0]*(n+1)
	#b , c = tin()
	#s = input()
	for _ in range(k):
		l, r = tin()
		dist = r - l
		imos[0]+=1
		pre = dist+1
		pa(('dist:',dist))
		for i in range(2, int(r**0.5)+1):
			if r % i <= dist:
				pa(('i:',i))
				if pre > i - dist:
					pass
				else:
					imos[pre]-=1
					imos[(i-1) - dist]+=1
				pre = r
		else:
			if pre > r - dist:
				pass
			else:
				imos[pre]-=1
				imos[(r-1) - dist]+=1
			pre = r
			imos[pre] -= 1
					
	ret=0
	print(imos)
	for v in imos:
		ret += v
		print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int, input().split());S=[[]for _ in range(m+1)];exec("l,r=map(int,input().split());S[r-l+1].append((l, r));"*n);B=[0]*(m+2)
def A(i,a):
 while i<=m+1:B[i]+=a;i+=i&(-i)
def C(i):
 r=0
 while i:r+=B[i];i-=i&(-i)
 return r
for i in range(1,m+1):
 for l,r in S[i]:n-=1;A(l,1);A(r+1,-1)
 r=n
 for j in range(0,m+1,i):r+=C(j)
 print(r)

Submission status: Time Limit Exceeded

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)}
for i in range(N):
    l,r=map(int,input().split())
    q[l].append(r)

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

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

imos=[0 for i in range(M+2)]
for i in range(1,M+1):
    for r in q[i]:
        imos[i]+=1
        imos[r+1]-=1

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

for i in range(1,M+1):
    res=imos[i*(M//i)]
    for j in range(M//i,1,-1):
        res+=qans[(i*j-i,i*j)]
    print(res)