Problem:
 Score : 400 points    Problem Statement Joisino is planning to record N TV programs with recorders.  The TV can receive C channels numbered 1 through C .  The i -th program that she wants to record will be broadcast from time s_i to time t_i (including time s_i but not t_i ) on Channel c_i .  Here, there will never be more than one program that are broadcast on the same channel at the same time.  When the recorder is recording a channel from time S to time T (including time S but not T ), it cannot record other channels from time S-0.5 to time T (including time S-0.5 but not T ).  Find the minimum number of recorders required to record the channels so that all the N programs are completely recorded.      Constraints  1≤N≤10^5  1≤C≤30  1≤s_i<t_i≤10^5  1≤c_i≤C  If c_i=c_j and i≠j , either t_i≤s_j or s_i≥t_j .  All input values are integers.         Input Input is given from Standard Input in the following format:  N  C  s_1  t_1  c_1  :  s_N  t_N  c_N       Output When the minimum required number of recorders is x , print the value of x .        Sample Input 1 3 2
1 7 2
7 8 1
8 12 1      Sample Output 1 2  Two recorders can record all the programs, for example, as follows:   With the first recorder, record Channel 2 from time 1 to time 7 . The first program will be recorded. Note that this recorder will be unable to record other channels from time 0.5 to time 7 .  With the second recorder, record Channel 1 from time 7 to time 12 . The second and third programs will be recorded. Note that this recorder will be unable to record other channels from time 6.5 to time 12 .        Sample Input 2 3 4
1 3 2
3 4 4
1 4 3      Sample Output 2 3  There may be a channel where there is no program to record.       Sample Input 3 9 4
56 60 4
33 37 2
89 90 3
32 43 1
67 68 3
49 51 3
31 32 3
70 71 1
11 12 3      Sample Output 3 2

Solution (Python):
import heapq
N, C, *STC = [int(_) for _ in open(0).read().split()]
STC = [(s, t, c) for s, t, c in zip(STC[::3], STC[1::3], STC[2::3])]
STC.sort()




class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_right(self, p, v):  
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(dat[p], v)
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_left(self, p, v):  
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(v, dat[p])
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        vl = vr = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                vl = f(vl, dat[l])
                l += 1
            if r & 1:
                r -= 1
                vr = f(dat[r], vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)

ti = (10 ** 10, -10 ** 10)
st = SegmentTree([(10 ** 10, i) for i in range(C + 1)], min, ti)
ans = 0
for s, t, c in STC:
    if st.query(c, c + 1)[0] == 10 ** 10:
        t2, c2 = st.query(1, C + 1)
        if t2 < s:
            st.update(c2, (10 ** 10, c2))
        else:
            ans += 1
    st.update(c, (t, c))
print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline




def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


from collections import deque

def main():
	n,c=MI()

	li=[[0]*c for _ in range(10**5+1)]
	

	for _ in range(n):
		s,t,cc=MI()
		for i in range(s-1,t):
			li[i][cc-1]=1

	ans=0

	for A in li:
		ans=max(ans,sum(A))
	print(ans)









if __name__ == "__main__":
	main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline




def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


from collections import deque

def main():
	n,c=MI()

	li=[[0]*c for _ in range(10**5+1)]
	

	for _ in range(n):
		s,t,cc=MI()
		for i in range(s-1,t):
			li[i][cc-1]=1

	ans=0

	for A in li:
		ans=max(ans,sum(A))
	print(ans)









if __name__ == "__main__":
	main()

Solution (Python):
N, C = map(int, input().split())
sch = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
rec = [[0, 0] for _ in range(C+1)]
num_rec = 1

for i in range(N):
    s, t, c = sch[i]
    start = False
    for j in range(1, num_rec + 1):
        if rec[j][0] - int(rec[j][1] == c) < s:
            rec[j] = [t, c]
            start = True
            break
    if not start:
        num_rec += 1
        rec[num_rec] = [t, c]
    
print(num_rec)

Solution (Python):
n,c=map(int,input().split())
imos=[[0 for i in range(c)] for j in range(10**5+1)]
for i in range(n):
    s,t,_c=map(int,input().split())
    imos[s-1][_c-1]+=1
    imos[t][_c-1]-=1
for i in range(1,10**5+1):
    for j in range(c):
        imos[i][j]+=imos[i-1][j]
imosans=[0]*(10**5+1)
for i in range(10**5+1):
    for j in range(c):
        imosans[i]+=(imos[i][j]>=1)
print(max(imosans))

Solution (Python):
imos = [0]*(10**5+2)

N,C = map(int,input().split())
C = 30
mitai = [[] for i in range(C+1)]

for i in range(N):
    s,t,c = map(int,input().split())
    mitai[c].append([s,t])

for i in range(C+1):
    mitai[i].sort()


for i in range(C+1):
    preT = -1
    for j in mitai[i]:
        s,t = j[0],j[1]
        if preT == s:
            imos[s+1]+=1
            imos[t+1]-=1
        else:
            imos[s]+=1
            imos[t+1]-=1
        preT = t

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

print(max(imos))

Solution (Python):
n,c=map(int,input().split())
a=[]
tf=0
for _ in range(n):
  s,t,ch=map(int,input().split())
  a+=[(ch,s,t)]
a=sorted(a)
flag=a[0][0]
ans=[0]*(10**5+1)
tf=0
for ch,s,t, in a:
  if ch==flag and tf==s:ans[s]+=1
  else:ans[s-1]+=1
  ans[t]-=1
  tf=t
  flag=ch
for i in range(10**5):
  ans[i+1]+=ans[i]
print(max(ans))

Solution (Python):
from itertools import accumulate
n, C = map(int, input().split())

U = 10**5
channels = [[0]*(U+1) for _ in range(C)]
for _ in range(n):
    s, t, c = map(lambda x: int(x)-1, input().split())
    channels[c][s] += 1
    channels[c][t] -= 1


for i in range(C):
    for j in range(U):
        channels[i][j+1] += channels[i][j]

schedules = [0]*(U+1)
for i in range(C):
    L = None
    for j in range(U+1):
        if channels[i][j] and L is None:
            L = j-1
            continue

        if not channels[i][j] and L is not None:
            schedules[max(L, 0)] += 1
            schedules[j] -= 1
            L = None

print(max(accumulate(schedules)))

Solution (Python):
import sys
import numpy as np
readline=sys.stdin.readline
read=sys.stdin.read

n,c,*stc=map(int,read().split())
m=2*10**5
cht=np.zeros((c,m+1),dtype='int64')
for s,t,ch in zip(*[iter(stc)]*3):
  cht[ch-1,2*s-1:2*t]=np.ones(2*t-2*s+1)
print(max(np.sum(cht,axis=0)))

Solution (Python):
import sys
import numpy as np
readline=sys.stdin.readline
read=sys.stdin.read

def main():
  n,c=map(int,readline().split())
  m=2*10**5
  stc=[list(map(int,l.split())) for l in read().splitlines()]
  cht=np.zeros((c,m+1),dtype='int64')
  for e in stc:
    cht[e[2]-1,2*e[0]-1:2*e[1]]=np.ones(2*e[1]-2*e[0]+1)
  print(max(np.sum(cht,axis=0)))

if __name__=='__main__':
  main()

Solution (Python):
import sys
import numpy as np
readline=sys.stdin.readline
read=sys.stdin.read

n,c=map(int,readline().split())
m=2*10**5
stc=[list(map(int,l.split())) for l in read().splitlines()]
cht=np.zeros((c,m+1),dtype='int64')
for e in stc:
  cht[e[2]-1,2*e[0]-1:2*e[1]]=np.ones(2*e[1]-2*e[0]+1)
print(max(np.sum(cht,axis=0)))

Solution (Python):
import sys
readline=sys.stdin.readline
read=sys.stdin.read

n,c=map(int,readline().split())
m=2*10**5
stc=[list(map(int,l.split())) for l in read().splitlines()]
cht=[[0]*(m+1) for _ in range(c)]
for e in stc:
  cht[e[2]-1][2*e[0]-1:2*e[1]]=[1 for _ in range(2*e[1]-2*e[0]+1)]
mnr=0
for i in range(1,m+1):
  mnr=max(mnr,sum(cht[ch][i] for ch in range(c)))
print(mnr)

Solution (Python):
n, c = map(int, input().split())
program = [[] for _ in range(c)]

for i in range(n):
  s, t, cc = map(int, input().split())
  program[cc-1].append((s, t))

count = [0]*(10**5+1)
for i in range(c):
  program[i].sort()
  l = len(program[i])
  judge = True
  for j in range(l-1):
    if judge:
      count[program[i][j][0]-1] += 1
    if program[i][j][1] == program[i][j+1][0]:
      judge = False
    else:
      judge = True
    if judge:
      count[program[i][j][1]] -= 1
  if l == 0:
    continue
  if judge:
    count[program[i][l-1][0]-1] += 1
  count[program[i][l-1][1]] -= 1

ans = 0
for i in range(10**5+1):
  if i != 0:
    count[i] += count[i-1]
  if ans < count[i]:
    ans = count[i]
print(ans)

Solution (Python):
N, C = map(int, input().split())
prog = [list(map(int, input().split())) for _ in range(N)]


tv = [[-1, 0] for i in range(C)]

prog.sort()

for p in prog:
    s, t, c = p
    for i in range(C):
        if tv[i][0] < s - 0.5 or tv[i][1] == c or tv[i][1] == 0:
            tv[i][0] = t
            tv[i][1] = c
            break


ans = 0
for i in range(C):
    if tv[i][0] > 0:
        ans += 1
    else:
        break

print(ans)

Solution (Python):
N , C = map(int,input().split())
tel = [[0,-1] for i in range(C)]
pro = [list(map(int,input().split())) for i in range(N)]
pro.sort()
for s , t , c in pro:
    for i in range(C):
        if tel[i][0] < s - 0.5 or tel[i][1] == c or tel[i][1] == -1:
            tel[i][0] = t
            tel[i][1] = c
            break
for i in range(C):
    if tel[i][1] == -1:
        print(i)
        exit()
print(C)

Solution (Python):
from collections import defaultdict
n,c=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(n)]

dd=defaultdict(lambda: [0]*(10**5+1))
for s,t,ch in s:
  for i in range(s,t+1):
    dd[ch][i]=1
ans=0
for i in range(10**5+1):
  cnt=0
  for ch in range(c+1):
    if dd[ch][i]==1:
      cnt+=1
  ans=max(ans,cnt)
print(ans)

Solution (Python):
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, C, *STC = map(int, read().split())

    P = [[] for _ in range(C)]
    for s, t, c in zip(*[iter(STC)] * 3):
        P[c - 1].append((s, t))

    M = 10 ** 5
    vec = [0] * (M + 2)
    for i in range(C):
        P[i].sort()
        for j, (s, t) in enumerate(P[i]):
            if j > 0 and s == P[i][j - 1][1]:
                vec[s] += 1
                vec[t] += -1
            else:
                vec[s - 1] += 1
                vec[t] += -1

    vec = list(accumulate(vec))

    print(max(vec))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,C = MI()
A = [[0]*(10**5+2) for i in range(C+1)]
for i in range(N):
    s,t,c = MI()
    A[c][s] += 1
    A[c][t+1] -= 1

from itertools import accumulate

for i in range(1,C+1):
    A[i] = list(accumulate(A[i]))



ans = 0
for j in range(10**5+2):
    ans = max(ans,sum(A[i][j] > 0 for i in range(1,C+1)))

print(ans)

Solution (Python):
import heapq
N, C = map(int, input().split())

stc = [list(map(int, input().split())) for _ in range(N)]

stc.sort()

lst = []
hq = [[-1, -1]]
heapq.heapify(hq)
ans = 1
for i in range(N):
    p = stc[i]
    q = heapq.heappop(hq)
    if p[0] < q[0]:
        heapq.heappush(hq, q)

        ans += 1

    elif p[0] == q[0]:
        lst = []
        jdg2 = True

        while p[0] == q[0] and p[2]>= q[1]:
            if p[2] == q[1]:

                jdg2 = False
            else:
                lst.append(q)
            if hq: q = heapq.heappop(hq)
            else: break
        if jdg2:
            ans += 1
        if p[0] != q[0] or p[2] < q[1]:
            heapq.heappush(hq, q)

        for k in lst:
            heapq.heappush(hq, k)

    heapq.heappush(hq, [p[1], p[2]])

print(ans)

Solution (Python):
import sys

N, C = map(int, sys.stdin.readline().split())



times = [[set() for _ in range(10**5 + 5)], [set() for _ in range(10**5 + 5)]]
max_t = 0
for _ in range(N):
    s, t, c = map(int, sys.stdin.readline().split())
    
    times[0][s-1].add(c)
    times[0][s].add(c)
    times[1][t].add(c)
    max_t = max(max_t, t)

ans = 0
recording = set()
for i in range(max_t + 5):
    recording -= times[1][i]
    recording |= times[0][i]
    ans = max(ans, len(recording))

print(ans)

Solution (Python):
import itertools
n, c = map(int, input().split())
cs = [[0]*(10**5+10) for _ in range(c+1)]

for i in range(n):
    s, t, ch = map(int, input().split())
    s += 1
    t += 1
    cs[ch][t] = s

for i in range(1,c+1):
    for j in range(1,10**5+10):
    
        if cs[i][cs[i][j]] != 0:
            start = cs[i][j]
            cs[i][j] = cs[i][start]
            cs[i][start] = 0


rsw = [0]*(10**5+10)

for i in range(1,c+1):
    for j in range(1,10**5+10):
    
        if cs[i][j] != 0:
            cs[i][j] -= 1
            rsw[cs[i][j]] += 1
            rsw[j] -= 1

print(max(itertools.accumulate(rsw)))

Solution (Python):
N,C=map(int,input().split())
Z=[list(map(int,input().split())) for i in range(N)]
Z.sort()
def judge(x):
  R=[[-1,-1] for i in range(x)]
  for i in range(N):
    for j in range(x):
      if R[j][1]==Z[i][2]:
        R[j][0]=Z[i][1]
        break
      if j==x-1:
        for k in range(x):
          if R[k][0]<Z[i][0]:
            R[k][0]=Z[i][1]
            R[k][1]=Z[i][2]
            break
          if k==x-1:
            return False
  return True

L,R,M=1,C,0
while L!=R:
  M=(L+R)//2
  if judge(M):
    R=M
  else:
    L=max(L+1,M)
print(L)

Solution (Python):
import sys
import queue

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 ddd(al, c):
	rcq = queue.PriorityQueue()
	for _ in range(c):
		rcq.put(0)
	for st, ed in al:
		earliest = rcq.get()
		
		if earliest >= st-0.5:
			return False
		rcq.put(ed)
	return True

def main():
	
	n, c = tin()
	
	dd=[[] for _ in range(c)]
	for _ in range(n):
		s, t, cv = tin()
		dd[cv-1].append((s,t))
	
	
	
	aal=[]
	for cl in dd:
		if len(cl)==0:
			continue
		cl.sort()
		sa, ta = cl[0]
		for s, t in cl[1:]:
			if ta == s:
				ta = t
			else:
				aal.append((sa, ta))
				sa,ta = s, t
		else:
			aal.append((sa, ta))
			
	
	aal.sort()
	
	for i in range(1, c+1):
		is_ok = ddd(aal, i)
		
		if is_ok:
			return i
	
	

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
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):



from collections import deque

N, C = map(int,input().split())
Mx = 10**5+1
sch = [[0]*Mx for _ in range(C)]
scht = [0]*Mx
plist = [[] for _ in range(C)]
for _ in range(N):
    s, t, c = map(int,input().split())
    plist[c-1].append((s,t))
for c, p in enumerate(plist):
    p.sort()
    prevt = 0
    for s, t in p:
        if prevt == s:
            sch[c][prevt] = 0
        else:
            sch[c][s] = 1
        sch[c][t] = -1
        prevt = t
    for i in range(1, Mx):
        if sch[c][i]==1:
            scht[i-1]+=1
        if sch[c][i]==-1:
            scht[i]-=1

for i in range(1, Mx):
    scht[i] += scht[i-1]

print(max(scht))

Solution (Python):
N, C = map(int, input().split())
rec = [[0]*C for _ in range(10**5)]
for _ in range(N):
  s, t, c = map(int, input().split())
  for i in range(s-1, t):
    rec[i][c-1] = 1

print(max([sum(rec[i]) for i in range(10**5)]))

Solution (Python):
import sys
from collections import deque
from itertools import accumulate
def input(): return sys.stdin.readline().strip()


def main():
    """
    全部の番組に対して、例えば[2, 4)->[1, 4)のように録画準備時間を確保してたけど、
    同一チャンネルなら、例えば[2, 4), [4, 6)のように続く場合レコーダーは１台で十分。。
    """
    N, C = map(int, input().split())
    channel = [[] for _ in range(C)]
    for _ in range(N):
        s, t, c = map(int, input().split())
        channel[c - 1].append((s, t))
    
    schedule = [0] * (10**5 + 3)
    for c in range(C):
        channel[c].sort()
        channel[c] = deque(channel[c])
        if not channel[c]: continue
        pre_s, pre_t = channel[c].popleft()
        while channel[c]:
            if pre_t == channel[c][0][0]:
                pre_t = channel[c][0][1]
                channel[c].popleft()
                continue
            schedule[pre_s - 1] += 1
            schedule[pre_t] -= 1
            pre_s, pre_t = channel[c].popleft()
        schedule[pre_s - 1] += 1
        schedule[pre_t] -= 1
    total = accumulate(schedule)
    print(max(total))

        
    



if __name__ == "__main__":
    main()

Solution (Python):
N, C = map(int, input().split())
max_size = 10 ** 5
record_list = [[int(i) - 1 for i in input().split()] for _ in range(N)]
ans_list = [0 for _ in range(max_size)]
for c in range(C):
    T = [0 for _ in range(max_size + 1)]
    for s, t, i in record_list:
        if i == c:
            T[s] += 1
            T[t + 1] -= 1
    for i in range(max_size):
        T[i + 1] += T[i]
    for i in range(max_size):
        ans_list[i] += T[i] > 0
print(max(ans_list))

Solution (Python):

n, C = map(int, input().split())
L = [tuple(map(int, input().split())) for _ in range(n)]
m = 10 ** 5
S = [0] * m
for i in range(1, C + 1):
    T = [0] * (m + 1)
    for s, t, c in L:
        if c == i:
            T[s - 1] += 1
            T[t] -= 1
    for i in range(m):
        T[i + 1] += T[i]
    for i in range(m):
        S[i] += T[i] > 0
print(max(S))

Solution (Python):

n, C = map(int, input().split())
L = [tuple(map(int, input().split())) for _ in range(n)]
m = 2 * 10 ** 5 + 2
S = [0] * m
for x in range(1, C + 1):
    T = [0] * m
    for s, t, c in L:
        if c == x:
            
            T[2 * s - 1] += 1
            T[2 * t] -= 1
    for i in range(1, m):
        T[i] += T[i - 1]
    for i in range(m):
        if T[i] > 0:
            S[i] += 1
print(max(S))

Solution (Python):
n, C = map(int, input().split())
L = [tuple(map(int, input().split())) for _ in range(n)]
L.sort()
tmp = [[] for _ in range(C)]
for s, t, c in L:
    if tmp[c - 1]:
        if tmp[c - 1][-1][1] == s:
            tmp[c - 1][-1][1] = t
            continue
    tmp[c - 1].append([s, t])
l = []
for v in tmp:
    for i in v:
        l.append(i)
l.sort()

r = [0] * C
for s, t in l:
    for i in range(C):
        if r[i] < s:
            r[i] = t
            break
print(sum(1 for i in r if i))

Solution (Python):
import numpy as np
N, C = map(int, input().split())
s = np.empty(N)
t = np.empty(N)
c = np.empty(N)
for i in range(N):
  s[i], t[i], c[i] =  map(int, input().split())
TimeTable = np.zeros((C,100001))
maxTime = 0
for i in range(N):
  channle = int(c[i] - 1)
  for j in range(int(s[i]),int(t[i])+1):
    TimeTable[channle,j] = 1
  if maxTime < t[i]:
    maxTime = t[i]
MaxRecode = 0
for i in range(int(maxTime)):
  Recode = np.sum(TimeTable[:,i])
  if Recode > MaxRecode:
    MaxRecode = Recode
print(int(MaxRecode))

Solution (Python):
n,C=list(map(int,input().split()))
part=[[0]*(3*10**5) for _ in range(31)]
part2=[0]*(3*10**5)

for _ in range(n):
    s,t,c=list(map(int,input().split()))

    part[c][s]+=1
    part[c][t]-=1

for i in range(1,C+1):
    for j in range(1,10**5+1):
        if part[i][j]==1:
            part2[2*j-1]+=1
        elif part[i][j]==-1:
            part2[2*j]-=1

ans=0
for i in range(1,2*10**5+1):
    part2[i]+=part2[i-1]
    ans=max(ans,part2[i])

print(ans)

Solution (Python):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr



def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod



def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


inf = 10 ** 18
mod = 10 ** 9 + 7

n,C = lr()
sc = [[] for i in range(C)]
sct = [0 for i in range(10**5+1)]
scts = [[0 for i in range(10**5+1)] for j in range(C)]
for i in range(n):
    s,t,c = lr()
    sc[c-1].append([s,t])
for i,S in enumerate(sc):
    pre = -1
    for s,t in S:
        if s == pre or s == pre+1:
            scts[i][s-1]=1
        for j in range(s,t+1):
            scts[i][j]=1
ans = 0
for i in range(10**5+1):
    pre = 0
    for j in range(C):
        pre+=scts[j][i]
    ans=max(ans,pre)
print(ans)

Solution (Python):
def Csum(a):
    b,c=[0],0
    for i in range(len(a)):
        c+=a[i]
        b.append(c)
    return b

n,c=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]
b=[[0]*(10**5+10) for i in range(c)]
for i in a:
    b[i[2]-1][i[0]-1]+=1
    b[i[2]-1][i[1]]-=1
b=[Csum(i) for i in b]
ans=[]
for i in range(10**5+10):
    d=0
    for j in range(c):
        if b[j][i]>0:
            d+=1
    ans.append(d)
print(max(ans))

Solution (Python):
N, C = map(int, input().split())
accu = [[0]*(10**5+10) for _ in range(C)]
for _ in range(N):
    s, t, c = map(int, input().split())
    accu[c-1][s] += 1
    accu[c-1][t+1] -= 1
for i in range(C):
    for j in range(1, 10**5+10):
        accu[i][j] += accu[i][j-1]
ans = 0
for i in range(10**5+10):
    tmp = 0
    for j in range(C):
        tmp += accu[j][i]>0
    ans = max(ans, tmp)
print(ans)

Solution (Python):



N,C = map(int,input().split())
s=[0]*N
t=[0]*N
c=[0]*N
f=[False]*C
yoyaku=[False]*C
L=[]
for i in range(N):
    s[i],t[i],c[i]= map(int,input().split())
    L.append( [s[i]-0.5,c[i]-1,1] )
    L.append( [t[i],c[i]-1,0] )

L.sort()

ans=0
tmp=0

for i,(time, ch, sw) in enumerate(L):
    if sw==1:
        if f[ch]==False:
            tmp +=1
            f[ch]=True
            ans = max(ans,tmp)
        else:
            yoyaku[ch]=True
    else:
        if yoyaku[ch]:
            yoyaku[ch]=False
        else:
            tmp -= 1
            f[ch]=False
   
print(ans)

Solution (Python):
import sys
read = sys.stdin.read
def main():
    n, c = map(int, input().split())
    d = {e: [0] * (c + 1) for e in range(100001)}
    d1 = [0] * 100001
    m = map(int, read().split())
    stc = zip(m, m, m)
    for s, t, c in stc:
        if d[s][c]:
            d1[s - 1] -= 1
            d1[s] += 1
        else:
            d[s][c] = 1
        if d[t][c]:
            d1[t - 1] -= 1
            d1[t] += 1
        else:
            d[t][c] = 1
        d1[s - 1] += 1
        d1[t] -= 1

    cur = 0
    r = 0
    for i1 in range(100001):
        cur += d1[i1]
        r = max(r, cur)
    print(r)

if __name__ == '__main__':
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N, C = MAP()
stc = [LIST() for _ in range(N)]
stc.sort(key=lambda x:(x[2], x[0]))

tmp_s = stc[0][0]
tmp_t = stc[0][1]
tmp_c = stc[0][2]

stc = stc[1:]
stc_new = []

for s, t, c in stc:
	if c == tmp_c and s == tmp_t:
		tmp_t = t
	else:
		stc_new.append((tmp_s, tmp_t))
		tmp_s = s
		tmp_t = t
		tmp_c = c
stc_new.append((tmp_s, tmp_t))

now = [0]*(10**5+1)

for s, t in stc_new:
	now[s-1] += 1
	now[t] -= 1

now_acc = list(accumulate(now))

print(max(now_acc))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *
import numpy as np


N, C = MAP()

n = [[] for _ in range(C)]
for _ in range(N):
	s, t, c = MAP()
	n[c-1].append((s, t))

m = [[] for _ in range(C)]

for i in range(C):
	if n[i] == []:
		continue
	n[i].sort(key = lambda y:y[0])
	s = n[i][0][0]
	t = n[i][0][1]
	L = len(n[i])
	n[i].append((0, 0))
	for j in range(L):
		if j < L and n[i][j][1] == n[i][j+1][0]:
			t = n[i][j+1][1]
		else:
			m[i].append((s, t))
			s = n[i][j+1][0]
			t = n[i][j+1][1]


cnt = [0]*(10**5+1)

for x in m:
	for s, t in x:
		cnt[s-1] += 1
		cnt[t] -= 1


cnt = list(accumulate(cnt))

print(max(cnt))

Solution (Python):
N, C = map(int, input().split())
tv = [[0]*C for _ in range(100000)]
for _ in range(N):
    s, t, c = map(int, input().split())
    for i in range(s-1, t): tv[i][c-1] = 1
print(max([sum(tv[i]) for i in range(100000)]))

Solution (Python):
n,c = map(int,input().split())
ab = []
for _ in range(n):
    s, t, cha = (int(x) for x in input().split())
    ab.append([s, t, cha])

ab = sorted(ab, key=lambda x: x[0])
ab = sorted(ab, key=lambda x: x[2])

for i in range(1,n):
    if ab[i][0] == ab[i-1][1] and ab[i][2] == ab[i-1][2]:
        ab[i][0] = ab[i-1][0]
        ab[i-1][0] = -1

time = [0]*(10**5+1)

for i in range(n):
    if ab[i][0] == -1:
        continue
    time[ab[i][0]-1] += 1
    time[ab[i][1]] -= 1

ans = 0
memo = 0

for i in time:
    memo += i
    ans = max(ans,memo)

print(ans)

Solution (Python):




import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,c=MI()
dp=[[0]*c for i in range(10**5+1)]
for i in range(n):
    s,t,ch=MI()
    for j in range(s,t+1):
        dp[j][ch-1]=1
mx=0

for i in range(10**5):
    u=sum(dp[i])
    if u>mx:
        mx=u
print(mx)

Solution (Python):
N, C = map(int, input().split())
stc = [list(map(lambda x:int(x), input().split())) for _ in range(N)]

stc = sorted(stc, key=lambda x:(x[2], x[0], x[1]))
l = []
i = N-1
s, t, c = 0, 0, 0
while i >= 0:
    if stc[i][2] == stc[i-1][2] and stc[i][0] == stc[i-1][1]:
        s = stc[i-1][0]
        if t == 0:
            t = stc[i][1]
        c = stc[i][2]
    else:
        if s != 0:
            l += [[s, t, c]]
            s, t, c = 0, 0, 0
        else:
            l += [stc[i]]

    i -= 1
        
imos = [0]*(2*10**5+1)
for s, t, c in l:
    imos[s-1] += 1
    imos[t] -= 1

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

print(max(imos))

Solution (Python):
n,C=map(int,input().split())

chs=[[] for i in range(31)]

for i in range(n):
    s,t,c=map(int,input().split())
    chs[c].append((s,t))

for q in range(len(chs)):
    ch=chs[q][:]
    ch.sort()
    new=[]
    if len(ch)<=1:
        continue
    else:
        now=ch[0]
        for i in range(1,len(ch)):
            if now[1]==ch[i][0]:
                now=(now[0],ch[i][1])
            else:
                new.append(now)
                now=ch[i]
        new.append(now)
        chs[q]=new[:]

tim=[0 for i in range(200002)]

for ch in chs:
    for pro in ch:
        tim[pro[0]*2-1]+=1
        tim[pro[1]*2]-=1

cnt=0
ans=0
for i in range(len(tim)):
    cnt+=tim[i]
    ans=max(ans,cnt)
print(ans)