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



Sample input:
3 2
1 7 2
7 8 1
8 12 1


Sample output:
2

Submission status: Accepted

Solution code:
def main():
    N,C=map(int,input().split())
    stc=[0]*N
    for i in range(N):
        abc=list(map(int,input().split()))
        stc[i]=abc

    a=[0]*(C+1)
    stc.sort(key=lambda x:(x[2],x[0]))
    c=1
    for i in range(N):
        while stc[i][2]!=c:
            c+=1
        if stc[i][2]==c:
            a[c]+=1
    for i in range(1,C+1):
        a[i]+=a[i-1]
    
    table=[0]*(2*10**5+2)
    for i in range(C):
        for j in range(a[i],a[i+1]):
            if j==a[i]:
                table[stc[j][0]*2-1]+=1
                table[stc[j][1]*2]-=1
            else:
                if stc[j-1][1]==stc[j][0]:
                    table[stc[j][0]*2]+=1
                    table[stc[j][1]*2]-=1
                else:
                    table[stc[j][0]*2-1]+=1
                    table[stc[j][1]*2]-=1                    
    M=0
    for i in range(len(table)):
        if 0<i:
            table[i]+=table[i-1]
    for i in range(len(table)):
        if M<table[i]:
            M=table[i]
    print(M)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
N,C = map(int,input().split())
STC = [tuple(map(int,input().split())) for i in range(N)]

cs = [[] for _ in range(30)]
for s,t,c in STC:
    cs[c-1].append((s,t))

imos = [0]*(100005)
for c in cs:
    c.sort(key=lambda x:x[0])
    pt = -1
    for s,t in c:
        if s==pt:
            imos[s] += 1
        else:
            imos[s-1] += 1
        imos[t] -= 1
        pt = t
for i in range(len(imos)-1):
    imos[i+1] += imos[i]
print(max(imos))

Submission status: Accepted

Solution code:
from itertools import accumulate
n,c=map(int,input().split())
time=[0]*(10**5+2)
stc=[]
for i in range(n):
	s,t,c=map(int,input().split())
	stc.append([s,t,c])
stc.sort(key=lambda x:(x[2],x[0]))
for i in range(n-1):
	if stc[i][2]==stc[i+1][2]:
		if stc[i][1]==stc[i+1][0]:
			stc[i+1][0]=stc[i][0]
			stc[i]=[-1]
lis=[]
for i in range(n):
	if stc[i]!=[-1]:
		lis.append(stc[i])
for i in range(len(lis)):
	time[lis[i][0]-1]+=1
	time[lis[i][1]]-=1
print(max(accumulate(time)))

Submission status: Accepted

Solution code:
from operator import itemgetter
N, C = list(map(int, input().split()))

BA = []
for i in range(N):
  BA.append(list(map(int, input().split())))

BA.sort(key=itemgetter(2,0,1))

# 0.5刻みのIMOS
IMO = [0] * (200010)
prev_c = -1
prev_t = -1
tmax = 0
for i in range(N):
  s, t, c = BA[i]
  if prev_c == c and prev_t == s:
    IMO[2*s+1] += 1
    IMO[2*t+1] -= 1
  else:
    IMO[2*s-1] += 1
    IMO[2*t+1] -= 1
    
  prev_t, prev_c = t,c
  tmax = max(tmax, t)
  
for i in range(2*tmax+5):
  IMO[i+1] += IMO[i]
  
print(max(IMO[:2*tmax+5]))
#print(IMO[:2*tmax+5])

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,c=map(int,input().split())
stc=[list(map(int,input().split())) for i in range(n)]
stc.sort(key=lambda x: x[2])
# print(stc)
lst=[[0]*(10**5+5) for i in range(c)]
for i in range(len(stc)):
    s,t,c=stc[i]
    for j in range(s-1,t):
        lst[c-1][j]+=1
anslst=[0]*(10**5+5)
for i in range(c):
    for j in range(10**5+5):
        if lst[i][j]!=0:
            anslst[j]+=1
print(max(anslst))

Submission status: Accepted

Solution code:
# チャンネルの情報は不要ではない, その情報を適切に使う必要がある
from itertools import accumulate
from collections import defaultdict
N, V = map(int, input().split())  # N個の録画したい番組, V個のチャンネル
programs = defaultdict(list)
for _ in range(N):
    s, t, c = map(int, input().split())
    programs[c].append((s, t))

imos = [0] * (100002)
for c, p in programs.items():  # cはチャンネルの番号, pは番組の開始と終了のペアのリスト
    p.sort()  # 開始時間が早い順にソート
    ps, pt = p[0]  # そのチャンネルで一番早い時間に始まる番組の開始と終了の時刻
    for s, t in p[1:]:
        if pt == s:  # もし直前の番組の終了時刻と今から始まる番組の開始時間が一緒なら繋げることができる
            pt = t
        else:
            # 繋げることができない場合、imos法を適用してpsとptを最新のものに変更する
            imos[ps-1] += 1  # ps-0.5を含むからps-1をインクリメントする？
            imos[pt] -= 1  # ptは含まないからptをデクリメントする
            ps, pt = s, t

    # forループでは最後の番組の録画を行っていないのでその処理
    imos[ps-1] += 1
    imos[pt] -= 1

print(max(accumulate(imos)))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

#heapq
import heapq
class Reverse:
    def __init__(self, val):
        self.val = val
        
    def __lt__(self, other):
        return self.val > other.val
        
    def __repr__(self):
        return repr(self.val)
    
class Heapq:
    def __init__(self, arr, desc = False):
        if desc:
            for i in range(len(arr)):
                arr[i] = Reverse(arr[i])
        self.desc = desc
        self.hq = arr
        heapq.heapify(self.hq)
 
    def pop(self):
        if self.desc: return heapq.heappop(self.hq).val
        else: return heapq.heappop(self.hq)
 
    def push(self, a):
        if self.desc: heapq.heappush(self.hq, Reverse(a))
        else: heapq.heappush(self.hq, a)
 
    def top(self):
        if self.desc: return self.hq[0].val
        else: return self.hq[0]


from operator import itemgetter
def index_sort(A):
    A_sort = sorted(enumerate(A),key=itemgetter(1))
    index = [a[0] for a in A_sort]
    sorted_A = [a[1] for a in A_sort]
    return index, sorted_A


N,C = II()
s,t,c = Line(N,3)

# 同じチャンネルで，空き時間なしで番組が続くときはまとめて録画する
new_s = []
new_t = []
tl = [[] for _ in range(C)]
for i in range(N):
    tl[c[i]-1].append((s[i],t[i]))
for j in range(C):
    if not tl[j]:
        continue
    tl[j].sort(key=itemgetter(0))
    sj = []
    tj = []
    start,last = tl[j][0][0],tl[j][0][1]
    for i in range(1,len(tl[j])):
        if tl[j][i][0] != last:
            sj.append(start)
            tj.append(last)
            start = tl[j][i][0]
            last = tl[j][i][1]
        else:
            last = tl[j][i][1]
    sj.append(start)
    tj.append(last)
    new_s.extend(sj)
    new_t.extend(tj)

index, _ = index_sort(new_s)
s = [new_s[i] for i in index]
t = [new_t[i] for i in index]

h = Heapq([10**6])
ans = 0
for i in range(len(s)):
    if h.top() < s[i]:
        h.pop()
        h.push(t[i])
    else:
        h.push(t[i])
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,c = map(int,input().split())
imos = [0 for i in range(10**5+1)]
stcl = []
for _ in range(n):
    s,t,c = map(int,input().split())
    stcl.append((s,t,c))
    imos[s-1] += 1
    imos[t] -= 1

stcl = sorted(stcl, key=lambda x: (x[2], x[1]))

new = []
s,t,c = stcl[0]
for i in range(1,n):
    if c == stcl[i][2] and t == stcl[i][0]:
        t = stcl[i][1]
    else:
        new.append((s, t, c))
        s, t ,c = stcl[i]
else:
    new.append((s, t, c))

imos = [0 for i in range(10**5+1)]
for s,t,c in new:
    imos[s-1] += 1
    imos[t] -= 1
import itertools
imos_ac = list(itertools.accumulate(imos))
print(max(imos_ac))

Submission status: Accepted

Solution code:

N, C = map(int, input().split())
stc = [list(map(int, input().split())) for _ in range(N)]
 
record = [[0] * 10 ** 5 for _ in range(C)]
for s, t, c in stc:
    for i in range(s, t + 1):
        record[c-1][i-1] = 1
 
ans = 0
for i in range(10 ** 5):
    cnt = 0
    for j in range(C):
        cnt += record[j][i]
    ans = max(ans, cnt)
 
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,c = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
a.sort(key=lambda x:x[0])
a.sort(key=lambda x:x[2])

# 同じチャンネルの番組を繋げる。
for i in range(n-1):
    if a[i][1]==a[i+1][0] and a[i][2]==a[i+1][2]:
        a[i][1]-=1
# いもす法
x=[0]*(10**5+5)
for i in range(n):
    x[a[i][0]]+=1
    x[a[i][1]+1]-=1

x = itertools.accumulate(x)
print(max(x))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7
INF = int(1e15)

T_MAX = int(1e05) + 1


def main():
    # sys.stdin = open("sample.txt")
    N, C = Scanner.map_int()
    S = [Scanner.map_int() for _ in range(N)]
    M = [[0 for _ in range(C)] for _ in range(T_MAX)]
    for i in range(N):
        M[S[i][0]-1][S[i][2]-1] += 1
        M[S[i][1]][S[i][2]-1] -= 1
    for c in range(C):
        for t in range(1, T_MAX):
            M[t][c] += M[t-1][c]
    ans = 0
    for t in range(T_MAX):
        ans = max(ans, M[t].count(1))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, c = map(int, input().split())
data = [[0 for i in range(c+1)] for j in range(10**5+2)]
for i in range(n):
    s, t, channel = map(int, input().split())
    data[s][channel] += 1
    data[t+1][channel] -= 1
for i in range(c+1):
    for j in range(1,10**5+2):
        data[j][i] += data[j-1][i]
ans = 0
for i in range(10**5+2):
    sum_channel = 0
    for j in range(c+1):
        if data[i][j] == 1:
            sum_channel += 1
    ans = max(ans, sum_channel)
print(ans)

Submission status: Accepted

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,C=map(int,input().split())
stc=[list(map(int,input().split())) for i in range(N)]
stc=sorted(stc,key=lambda x:x[0])
#print(stc)
rokugaki=[]
for s,t,c in stc:

    a=[i for i in range(len(rokugaki)) if rokugaki[i][1]==c]
    if not a:
        a=[i for i in range(len(rokugaki)) if rokugaki[i][0]<s]
    if a:
        rokugaki[a[0]]=[t,c]

    else:
        rokugaki.append([t,c])
    #print(rokugaki)

print(len(rokugaki))

Submission status: Accepted

Solution code:
import numpy as np
n, c = map(int, input().split())
channels = np.zeros((30, 10**5), dtype=np.int64)
for _ in range(n):
  s, t, c = map(int, input().split())
  s -= 1
  t -= 1
  c -= 1
  channels[c, s:t+1] += 1
newchannels = np.where(channels>1, 1, channels)
sums = newchannels.sum(axis=0)
print(sums.max())

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
g=[[0]*3 for i in range(n)]
for i in range(n):
  g[i]=list(map(int,input().split()))
g.sort(key=lambda x: x[0])
g.sort(key=lambda x: x[2])
T=[0]*(10**5+3)
i=0
while i<n:
  if i!=n-1 and g[i][2]==g[i+1][2] and g[i][1]==g[i+1][0]:
    T[g[i][0]]+=1
    i=i+1
    T[g[i][1]]-=1
    i=i+1
  else:
    T[g[i][0]]+=1
    T[g[i][1]+1]-=1
    i=i+1
ans=0
a=0
for i in range(len(T)):
  a=a+T[i]
  if a>ans:
    ans=a
print(ans)

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,c = inm()
a = []
for i in range(n):
    s,t,c = inm()
    a.append((t,s,c))
a.sort()

h = {}  # h[(t,c)] = s
for z in a:
    t,s,c = z
    if (s,c) in h:
        s0 = h[(s,c)]
        del h[(s,c)]
        h[(t,c)] = s0
    else:
        h[(t,c)] = s

a = []
for z in h:
    t,c = z
    s = h[z]
    a.append((t,s,c))

a.sort()
#ddprint(a)
n = len(a)
nu = 0
ut = [-1]*n
uc = [-1]*n
for i in range(n):
    t,s,c = a[i]
    #ddprint("lp t {} s {} c {} i {}".format(t,s,c,i))
    mx = -1
    for j in range(nu):
        if ut[j] <= s-1 and ut[j]>mx:
            mx = ut[j]
            mxj = j
            if False:
                ddprint("t {} s {} c {} j {}".format(t,s,c,j))
                ddprint(ut)
                ddprint(uc)
    if mx == -1:
        mxj = nu
        nu += 1
    ut[mxj] = t
    uc[mxj] = c
    #ddprint(mxj)
print(nu)

Submission status: Accepted

Solution code:
from itertools import accumulate
N, C = map(int, input().split())
R = [0] * (10**5+1)
RC = [[] for _ in range(C)]
for _ in range(N):
    s, t, c = map(int, input().split())
    RC[c-1].append((s,t))

for rc in RC:
    rc.sort()
    pt = 0
    for s, t in rc:
        if s == pt:
            R[pt] += 1
        else:
            R[s-1] += 1
        R[t] -= 1
        pt = t
print(max(list(accumulate(R))))

Submission status: Accepted

Solution code:
import numpy as np
N, C = map(int, input().split())
dic = []
L = 0
for i in range(N):
  s, t, c = map(int, input().split())
  dic += [(c-1,s,t)]
  if 2*t+1>L:
    L = 2*t+1

sm = np.zeros(L)
for c in range(C):
  tt = np.zeros(L)
  for i in range(N):
    if dic[i][0]==c:
      tt[dic[i][1]*2-1] += 1
      tt[dic[i][2]*2] -= 1
  tt = tt.cumsum()
  sm[tt>0] += 1
print(int(sm.max()))

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
dic = []
for i in range(N):
  s, t, c = map(int, input().split())
  dic += [(c-1,s,t)]

L = 2*100000+1
sm = [0]*L
for c in range(C):
  tt = [0]*(L)
  for i in range(N):
    if dic[i][0]==c:
      tt[dic[i][1]*2-1] += 1
      tt[dic[i][2]*2] -= 1
  for i in range(1,L):
    tt[i] += tt[i-1]
  for i in range(L):
    if tt[i]>0:
      sm[i] += 1
print(max(sm))

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
tmp = []

for _ in range(N):
    s, t, c = map(int, input().split())
    tmp.append((s, t, c))
tmp.sort()

# そもそもCが小さいから力技で行けるはず
video = [(0, 0)]  # t,c
for s, t, c in tmp:
    for i, v in enumerate(video):
        ti, ci = v
        if c == ci:
            video[i] = (t, c)
            break
        if s > ti:
            video[i] = (t, c)
            break
    else:
        video.append((t, c))
    video.sort(reverse=True)

ans = len(video)
print(ans)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
from itertools import accumulate
def resolve():
    end=100000
    input=sys.stdin.readline
    N,C=map(int,input().rstrip().split())
    S=[list(map(int,input().rstrip().split())) for _ in range(N)]

    l=[[0 for _ in range(C)] for __ in range(2*end)]
    for i in range(N):
        l[S[i][0]*2-1][S[i][2]-1]+=1
        if S[i][1]!=end:
            l[S[i][1]*2+1][S[i][2]-1]-=1
    """
    ans=0
    npl=np.array(l)
    for i in range(C):
        snpl=npl[:,i]
        buf=list(snpl)
        asum = list(accumulate(buf))
        M=max(asum)
        ans=max(ans,M)
    """
    asum=[0 for __ in range(2*end)]
    for i in range(2*end):#列(C)で和を取る
        for j in range(C):
            asum[i]+=l[i][j]
    asum2=list(accumulate(asum))
    ans=max(asum2)
    ans=min(ans,C)

    print(int(ans))

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 2
1 7 2
7 8 1
8 12 1"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """3 4
1 3 2
3 4 4
1 4 3"""
        output = """3"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """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"""
        output = """2"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
n, c = map(int, input().split())
r = [[0 for i in range(c)] for j in range(100000)]  # テレビ局の番組表
for dummy in range(n):  # 入力
    s, t, c = map(int, input().split())
    for j in range(s - 1, t):
        r[j][c - 1] = 1  # 放送中なら1
ans = 0
for i in range(100000):
    if sum(r[i]) > ans:
        ans = sum(r[i])  # 同時に放送されている番組の最大数
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,C=map(int,input().split())
lena=10**5+1
a=[[0]*lena for _ in range(C+1)]
for i in range(N):
    s,t,c=map(int,input().split())
    a[c][s]+=1
    a[c][t]+=-1
#print(a)
for i in range(C+1):
    for j in range(1,lena):
        a[i][j]+=a[i][j-1]
#print(a)
for i in range(C+1):
    for j in range(1,lena):
        if a[i][j]==1:
            a[i][j-1]=1
#print(a)

for i in range(lena):
    for j in range(1,C+1):
        a[j][i]+=a[j-1][i]

ans=0
#print(a)
for i in range(lena):
    ans=max(ans,a[C][i])
print(ans)

Submission status: Accepted

Solution code:
n, c = map(int, input().split(" "))

time = list()
for i in range(0, n):
    s, t, c = map(int, input().split(" "))
    time.append((s, t, c))

time_sorted = sorted(time, key=lambda x: (x[2], x[1]))

time_joined = list()
prev = None
for current in time_sorted:
    if prev is None:
        prev = current

    elif prev[2] == current[2] and prev[1] == current[0]:
        prev = (prev[0], current[1], current[2])

    else:
        time_joined.append(prev)
        prev = current

time_joined.append(prev)
# print(time_joined)

time_list = list()
for s, t, c in time_joined:
    time_list.append((s - 0.5, "s"))
    time_list.append((t, "t"))

time_list_sorted = sorted(time_list, key=lambda x: x[0])

current = 0
ans = 0

for t, s in time_list_sorted:
    if s == "s":
        current += 1
        ans = max(ans, current)
    else:
        current -= 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline
N,C = map(int,input().split())
p = [list(map(int,input().split())) for i in range(N)]
p.sort()
ch = [[0,0] for i in range(C+1)]
p_true = []
for i in range(N):
  [s,t,c] = p[i]
  if ch[c][1] == s:
    ch[c][1] = t
  elif ch[c] == [0,0]:
    ch[c] = [s,t]
  else:
    p_true.append([ch[c][0],ch[c][1],c])
    ch[c] = [s,t]
for i in range(1,C+1):
  if ch[i] != [0,0]:
    p_true.append([ch[i][0],ch[i][1],i])
p_true.sort()
time = [0 for i in range(100002)]
for i in range(len(p_true)):
  [s,t,c] = p_true[i]
  time[s] += 1
  time[t+1] -= 1
print(max(accumulate(time)))

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
p=[list(map(int,input().split())) for _ in range(n)]
p.sort()
res = [0 for _ in range(100005)]
res0 = [[0,0] for _ in range(c)]
np = []
for s,t,c in p:
    if res0[c-1][0] == 0:
        res0[c-1] = [s,t]
    elif res0[c-1][1] ==s:
        res0[c-1][1] =t
    else:
        np.append(res0[c-1][:])
        res0[c-1]=[s,t]
for sres0 in res0:
    if sres0 != [0,0]:
    	np.append(sres0)

for s,t in np:
    res[s] += 1
    res[t+1]-=1

ress = [0]
for i in range(100005):
    ress.append(ress[-1]+res[i])

print(max(ress))

Submission status: Accepted

Solution code:
N,C=[int(x) for x in str(input()).split()]
A=[]
for i in range(N):
  a,b,d=[int(x) for x in str(input()).split()]
  A.append([d,a,b])


br=200002

count=[0 for i in range(br)]

A.sort()
for i in range(1,C+1):
  ind=[0 for i in range(br)]
  end=0
  for j in range(N):
    if A[j][0]==i:
      if end!=A[j][1]:
        end=A[j][2]
        ind[2*A[j][1]-1]=1
        ind[2*end]=-1
      else:
        end=A[j][2]
        ind[2*A[j][1]]=0
        ind[2*end]=-1
  temp=0
  for j in range(br):
    temp+=ind[j]
    if temp>0:
      count[j]+=1

print(max(count))

Submission status: Accepted

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


n, c = map(int, input().split())
tv_guide = []
for _ in range(n):
    start, end, channel = map(int, input().split())
    tv_guide.append([start, 1, channel-1])
    tv_guide.append([end, 0, channel-1])

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

channel_count = [0] * c
channel_set = set()
ans = 0
for time, on, channel in tv_guide:
    if on:
        channel_set.add(channel)
        channel_count[channel] += 1

    else:
        channel_count[channel] -= 1
        if channel_count[channel] == 0:
            channel_set.discard(channel)

    candidate = len(channel_set)
    if ans < candidate:
        ans = candidate

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline


n, c = map(int, input().split())
tv_guide = np.zeros((c, 10**5+1), dtype=np.int)

for _ in range(n):
    s, t, c = map(lambda x: int(x)-1, input().split())
    tv_guide[c][s:t+1] = 1

ans = 0
for time in range(10**5+1):
    count = sum(tv_guide[:,time])
    ans = max(count, ans)

print(ans)

Submission status: Accepted

Solution code:
def main():
    input_string = list(map(int,input().split()))
    N = input_string[0]
    C = input_string[1]
    data = []
    max_time = 0
    for i in range(N):
        data.append(list(map(int,input().split())))
        max_num = max(data[i])
        if max_num>max_time:
            max_time=max_num

    #data_np = np.array(data).reshape(N,3)
    #data_np = np.array(data)

    #max_time = int(max(data))
    #print("max",max_time)
    schedule = [[0]*C for i in range(max_time)]
    #schedule = np.zeros([max_time,C])

    for i in range(N):
        start = data[i][0]-1
        end = data[i][1]-1
        channel = data[i][2]-1
        for j in range(end-start+1):
            if start+j-1<0:continue
            schedule[start+j-1][channel] = 1

#    for c in range(C):
#        for t in range(max_time):
#            if t==0:continue
#            if schedule[t][c]==1 and schedule[t-1][c]==0:
#                schedule[t-1][c]=1

    #max_N =0
    #for t in range(max_time):
    #    sum_of_ch = sum(schedule[t])

    temp = list(map(sum,list(schedule)))
    max_N = int(max(temp))


    #    if sum_of_ch>max_N:
    #        max_N = int(sum_of_ch)
    print(max_N)







main()

Submission status: Accepted

Solution code:
# ABC080 D - Recording
N,C = map(int,input().split())
T = [[0 for _ in range(C)] for j in range(100001)]
for i in range(N):
    s,t,c = map(int,input().split())
    for j in range(s-1,t):
        T[j][c-1] = 1
ans = 0
for i in range(100001):
    sumT = sum(T[i])
    if ans < sumT:
        ans = sumT
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = MAP()
C = [[] for i in range(M)]
for i in range(N):
    l, r, c = MAP()
    c -= 1
    C[c].append((l, r))

# 同チャンネルで連続する区間をまとめる
LR = []
for i in range(M):
    if C[i]:
        C[i].sort()
        LR.append(C[i][0])
        for j in range(1, len(C[i])):
            l1, r1 = C[i][j-1]
            l2, r2 = C[i][j]
            if r1 == l2:
                LR.pop()
                LR.append((l1, r2))
                # 3連続以上を考慮して更新
                C[i][j] = (l1, r2)
            else:
                LR.append((l2, r2))

# いもす法
MAX = 10 ** 5 + 7
imos = [0] * MAX
for l, r in LR:
    imos[l-1] += 1
    imos[r] -= 1
imos = list(accumulate(imos))
print(max(imos))

Submission status: Accepted

Solution code:
import sys

inf = float('inf')

n, C, *stc = map(int, sys.stdin.read().split())
stc = list(zip(*[iter(stc)] * 3))

def main():
    res = [(-0.5, None) for _ in range(C)] # C台あれば確実に足りる
    stc.sort()

    for s, t, c in stc:
        c -= 1
        interval = inf
        for i in range(C):
            last, prev = res[i]
            if prev != c:
                last += 0.5

            if last <= s:
                if s - last < interval:
                    interval = s - last
                    to_use = i
        res[to_use] = (t, c)
    
    ans = 0
    for i in range(C):
        if res[i][0] != -0.5:
            ans += 1
    return ans

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
bangumi=[tuple(map(int,input().split())) for i in range(n)]
jikan=[0]*(10**5+1)

#チャンネルごとにソート
from operator import itemgetter
bangumi=sorted(bangumi, key=itemgetter(2,0))

nowch=0
syuryo=0
for s,t,c in bangumi:
  if c==nowch and s==syuryo:
    for i in range(s+1,t+1): #時刻Sでの重複数え上げを防ぐ
      jikan[i]+=1
  else:
    for i in range(s,t+1):
      jikan[i]+=1
  nowch=c
  syuryo=t

#print(bangumi)
print(max(jikan))

Submission status: Accepted

Solution code:
N,C = map(int,input().split())
ch = {}
for _ in range(N):
    s,t,c = map(int,input().split())
    if c not in ch:
        ch[c] = [0 for _ in range(2*10**5+2)]
    for i in range(2*s-1,2*t):
        ch[c][i]=1
cmax = 0
for i in range(2*10**5+2):
    cnt = 0
    for c in ch:
        if ch[c][i]==1:
            cnt += 1
    cmax = max(cmax,cnt)
print(cmax)

Submission status: Accepted

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

max_t = 0
for s, t, c in stc:
  max_t = max(max_t, t)

T = [[0 for _ in range(max_t + 2)] for _ in range(C + 1)] 
for i in range(N):
  s, t, c = stc[i]
  T[c][s] = t - s + 1
#print("T:", T[1:])

for c in range(1, C + 1):
  for i in range((max_t + 2) - 1):
    if T[c][i]:
      if T[c][i + 1] == 0:
        T[c][i + 1] = T[c][i] - 1
      T[c][i] = 1      
#print("T:", T[1:])

answer = []
for i in range(max_t + 2):
  cnt = 0
  for c in range(1, C + 1):
    if T[c][i]:
      cnt += 1
  answer.append(cnt)
#print("answer:", answer)
print(max(answer))

Submission status: Accepted

Solution code:

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

simu = [[0]*(30) for _ in range(10**5+1)]
tmp = 0
for j in range(30):
    simu[0][j] += rec[0][j]
    tmp += simu[i][j]
ans = tmp
for i in range(1,10**5+1):
    tmp = 0
    for j in range(30):
        simu[i][j] += simu[i-1][j] + rec[i][j]
        tmp += simu[i][j]
    ans = max(ans,tmp)
print(ans)

Submission status: Accepted

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

STC = [tuple(map(int, input().split())) for i in range(N)]
STC.sort()

rec = []
for i in range(N):
    isFree = False
    for j in range(len(rec)):
        if (rec[j][0] < STC[i][0] and rec[j][1] != STC[i][2]) or (rec[j][0] <= STC[i][0] and rec[j][1] == STC[i][2]):
            isFree, rec[j] = True, (STC[i][1], STC[i][2])
            break
    if not isFree:
        rec.append((STC[i][1], STC[i][2]))

print(len(rec))

Submission status: Accepted

Solution code:
from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7

input = sys.stdin.readline
#最初にソートしてるのに何故かヒープ使ってハマった
def main():
    n, c = map(int, input().split())
    stk = [tuple(map(int, input().split())) for i in range(n)]
    stk = sorted(stk, key=lambda x: x[0])

    ans = 1
    l = []
    l = [(stk[0][1], stk[0][2])]
    for i in range(1, n):
        ll = []
        for j in range(len(l)):
            v = l[j]
            if stk[i][2] == v[1]:
                if stk[i][0] < v[0]:
                    ll.append(v)
            else:
                if stk[i][0] - 0.5 < v[0]:
                    ll.append(v)
        ll.append(stk[i][1:])
        l = ll
        ans = max(ans, len(l))
    print(ans)


if __name__ == '__main__':
    main()