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:
import sys
input = sys.stdin.readline

N, C = (int(i) for i in input().split())

pp = [[0] * 100001 for i in range(C)]

for i in range(N):
    s, t, c = (int(i) for i in input().split())
    for j in range(s, t+1):
        pp[c-1][j] = 1

res = 0
for i in range(100001):
    cc = 0
    for j in range(C):
        if pp[j][i]:
            cc += 1
    res = max(res, cc)

print(res)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N,C=list(map(int,input().split()))

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

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

ans=0
cnt=0
tmp=0
recorder = [(10**10,31)]

for x in arr:
    s, t, c= x
    while recorder[0][0]<s:
        heappop(recorder)
        cnt-=1
        cnt+=tmp
        tmp=0
    
    for i in range(len(recorder)):
        if recorder[i][0] == s and recorder[i][1] ==c:
            cnt-=1
            tmp+=1
            break
    heappush(recorder,(t,c))
    cnt+=1
    if ans < cnt:
        ans=cnt            
print(ans)

Submission status: Accepted

Solution code:
N, C = map( int, input().split())
timetable = [ [0]*(10**5) for _ in range(C)]
for _ in range(N):
    s,t,c = map( int, input().split())
    timetable[c-1][s-1:t] = [1]*(t-s+1)
# for c in range(C):
#     print(timetable[c][:20])
ans = 0
for i in range(10**5):
    now = 0
    for c in range(C):
        now += timetable[c][i]
    if ans < now:
        ans = now
print(ans)

Submission status: Accepted

Solution code:
INF = 10**5
N,C = map(int,input().split())
table = [0]*(INF+1)
prog = [list(map(int,input().split())) for i in range(N)]
prog.sort(key=lambda x:x[0])
cs = [set() for i in range(INF+1)]
for s,t,c in prog:
    cs[s].add(c)
for i in range(N):
    table[prog[i][0]-1] += 1
    if prog[i][2] in cs[prog[i][1]]:
        table[prog[i][1]-1] -= 1
    else:
        table[prog[i][1]] -= 1
ans,tmp = 0,0
for i in range(INF+1):
    tmp += table[i]
    ans = max(tmp,ans)
print(ans)

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
latest = 0
P = [[] for i in range(C)]
for i in range(N):
    s, t, c = map(int, input().split())
    P[c-1].append((s, t))
    latest = max(latest, t)

Dup = [0 for i in range(latest + 2)]
for i in range(C):
    P[i].sort()
    for j in range(len(P[i])):
        Dup[P[i][j][0]] += 1
        Dup[P[i][j][1] + 1] -= 1
        if j >= 1:
            if P[i][j][0] == P[i][j-1][1]:
                Dup[P[i][j][0]] -= 1
                Dup[P[i][j][0] + 1] += 1
for i in range(1, latest + 2):
    Dup[i] += Dup[i-1]
print(max(Dup))

Submission status: Accepted

Solution code:
N,C=map(int,input().split())
Time=[[0]*(10**5+1) for c in range(C)]
for i in range(N):
  s,t,c=map(int,input().split())  
  Time[c-1][s-1:t] = [1]*(t-s+1)
Times=max(map(sum,zip(*Time)))
print(Times)

Submission status: Accepted

Solution code:
n, c = map(int, input().split())
r = []
for i in range(n):#h:高さ
    r.append([int(m) for m in input().split()])

r.sort(key=lambda x:(x[0], x[1],x[2]))

xli = []
p = 0
for i in range(n):
    if i == 0:
        xli.append(r[i])
    else:
        xli.sort(key=lambda x: (x[1]), reverse=True)
        for jnum, j in enumerate(xli, 0):
            if (j[1] < r[i][0]) or (j[1] <= r[i][0] and j[2] == r[i][2]):
                p = 1
                xli[jnum] = r[i]
                break
        if p == 0:
            xli.append(r[i])
        p = 0

print(len(xli))

Submission status: Accepted

Solution code:
n, c = map(int, input().split())
r = []
for i in range(n):#h:高さ
    r.append([int(m) for m in input().split()])

r.sort(key=lambda x:(x[0], x[1],x[2]))

xli = []
p = 0
for i in range(n):
    if i == 0:
        xli.append(r[i])
    else:
        for jnum, j in enumerate(xli, 0):
            if (j[1] < r[i][0]) or (j[1] <= r[i][0] and j[2] == r[i][2]):
                p = 1
                xli[jnum] = r[i]
                break
        if p == 0:
            xli.append(r[i])
        p = 0

print(len(xli))

Submission status: Accepted

Solution code:
import numpy as np
n,c=map(int, input().split())
a=[list(map(int, input().split())) for  i in range(n)]
a.sort(key=lambda x: (x[2],x[0]))
ans=np.array([0]*3*10**5)
channel,last=0,0
for i,j,k in a:
    if channel==k and last==i:
        ans[i*2+1:j*2+1]+=1
        last=j
    else:
        ans[i*2-1:j*2+1]+=1
        last=j
        channel=k
print(ans.max())

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
M = 200005
rec = [[0] * M for i in range(C)]
for i in range(N):
    s, t, c = map(int, input().split())
    rec[c - 1][2 * s - 1] += 1
    rec[c - 1][2 * t] -= 1

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

num = 0
for j in range(M):
    tmp = 0
    for i in range(C):
        if rec[i][j] >= 1:
            tmp += 1
    num = max(tmp, num)

print(num)

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]
N, C = inpl()
channel = [[] for _ in range(C)]
for i in range(N):
    s, t, c = inpl()
    channel[c-1].append([s,t])
H = [0 for i in range(10**5+3)]
for i in range(C):
    channel[i].sort(key = lambda x: x[0])
    for j in range(len(channel[i])-1):
        if channel[i][j][1] == channel[i][j+1][0]:
            channel[i][j+1] = [channel[i][j][0],channel[i][j+1][1]]
            channel[i][j] = []
    channel[i] = [k for k in channel[i] if k != []]

for i in range(C):
    for st, en in channel[i]:
        H[st] += 1
        H[en+1] -= 1
ans = H[0]
for i in range(10**5+1):
    H[i+1] += H[i]
    ans = max(ans,H[i+1])
        
print(ans)

Submission status: Accepted

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

for i in range(C):
    G[i] = list(accumulate(G[i]))

ans = 0
for i in range(10 ** 5 + 1):
    tmp = 0
    for c in range(C):
        tmp += min(1, G[c][i])
    ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
from operator import attrgetter


class Data:
    def __init__(self, s, t, c):
        self.s = s
        self.t = t
        self.c = c


N, C = map(int, input().split())
data_list = []
for _ in range(N):
    s, t, c = map(int, input().split())
    data_list.append(Data(s, t, c))

ch_map = {}
for data in data_list:
    if data.c in ch_map:
        ch_map[data.c].append(data)
    else:
        ch_map[data.c] = [data]
data_list = []

m = {}
for key, val in ch_map.items():
    ch_list = sorted(val, key=attrgetter("s"))
    # m = {}
    ch_m = {}
    end = 0
    for ch in ch_list:
        if end <= ch.s:
            for i in range(ch.s-1, ch.t):
                if i in m:
                    if i not in ch_m:
                        m[i] += 1
                else:
                    m[i] = 1
                ch_m[i] = 1
                # m[i] = 1
            end = ch.t
        elif end > ch.t:
            for i in range((end+1, ch.t)):
                if i in m:
                    if i not in ch_m:
                        m[i] += 1
                else:
                    m[i] = 1
                ch_m[i] = 1
                # m[i] = 1
            end = ch.t
    # ch_map[key] = m


max = 0
for key, val in m.items():
    if max < val:
        max = val

# print(ch_map)
'''
for i in range(100001):
    cnt = 0
    for key, val in ch_map.items():
        if i in val:
            cnt += 1
    if cnt > max:
        max = cnt
    cnt = 0
'''
print(max)

Submission status: Accepted

Solution code:
N,C = map(int,input().split())
cum = [0]*(10**5+1)
tail = {}
head = {}
for i in range(10**5+1):
    tail[i] = []
    head[i] = []
for i in range(N):
    s,t,c = map(int,input().split())
    if c not in tail[s] and c not in head[t-1]:
        cum[s-1] += 1
        cum[t] -= 1
    elif c not in head[t-1]:
        cum[s] += 1
        cum[t] -= 1
    elif c not in tail[s]:
        cum[s-1] += 1
        cum[t-1] -= 1
    else:
        cum[s] += 1
        cum[t-1] -= 1
    tail[t].append(c)
    head[s-1].append(c)
    
import numpy as np
print(np.cumsum(cum).max())

Submission status: Accepted

Solution code:
N,C = map(int,input().split())
r = [[0]*(10**5) for c in range(C)]
for i in range(N):
    s,t,c = map(int,input().split())
    r[c-1][s-1:t] = [1]*(t-s+1)
print(max(map(sum,zip(*r))))

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
M = 10 ** 5 * 2 + 5
T = [[0] * M for i in range(C)]
for i in range(N):
    s, t, c = map(int, input().split())
    s = 2 * s - 1
    t = 2 * t
    c -= 1
    T[c][s] += 1
    T[c][t] -= 1

TT = [[0] * (2 * N) for i in range(C)]
for i in range(C):
    for j in range(1, M):
        T[i][j] += T[i][j - 1]

num = 0
for j in range(M):
    tmp = 0
    for i in range(C):
        if T[i][j] >= 1:
            tmp += 1

    num = max(tmp, num)
print(num)

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
stc=[list(map(int,input().split())) for _ in range(n)]
ts=[t[1] for t in stc]
mst=max(ts)
xstc=[[] for _ in range(c)]
for i in range(n):
    xstc[stc[i][2]-1].append([stc[i][0],stc[i][1]])
for i in range(c):
    xstc[i]=sorted(xstc[i],key=lambda x:x[0])
    for j in range(1,len(xstc[i])):
        if xstc[i][j-1][1]==xstc[i][j][0]:
            xstc[i][j][0]=xstc[i][j-1][0]
            xstc[i][j-1]=[]
z=[]
for i in range(c):
    for j in range(len(xstc[i])):
        if len(xstc[i][j])>0:
            z.append(xstc[i][j])
x=[0 for _ in range(mst+2)]
for i in range(len(z)):
    x[z[i][0]-1]+=1
    x[z[i][1]]-=1
for i in range(1,mst+2):
    x[i]+=x[i-1]
print(max(x))

Submission status: Accepted

Solution code:
import numpy as np


N, C_num = map(int, input().split(" "))
S, T, C = [], [], []
for _ in range(N):
    s, t, c = map(int, input().split(" "))
    S.append(s * 2 - 1)
    T.append(t * 2)
    C.append(c - 1)

table = np.zeros((C_num, 10 ** 5 * 3), "int32")
for s, t, c in zip(S, T, C):
    table[c, s:t] = 1

print(table.sum(0).max())

Submission status: Accepted

Solution code:
n, c = map(int, input().split())
tv = [list(map(int, input().split())) for i in range(n)]

tv.sort(key=lambda x: x[1])
imos = [0 for i in range(10**5+2)]
mark = [[] for i in range(10**5+2)]
for i in range(n):
    flag = 0
    for j in mark[tv[i][0]]:
        if j == tv[i][2]:
            flag = 1
    if flag:
        imos[tv[i][0]+1] += 1
    else:
        imos[tv[i][0]] += 1
    imos[tv[i][1]+1] -= 1
    mark[tv[i][1]].append(tv[i][2])

for i in range(10**5+1):
    imos[i+1] += imos[i]

print(max(imos[:-1]))

Submission status: Accepted

Solution code:
N,C = map(int,input().split())
src = [list(map(int,input().split())) for i in range(N)]
MAX = 10**5
bucket = [[] for i in range(MAX+2)]
bucket2 = [set() for i in range(MAX+2)]
for s,t,c in src:
    bucket[s].append((t,c))
    bucket2[s].add(c)

imos = [0]*(MAX+2)

for s in range(MAX):
    for t,c in bucket[s]:
        imos[s-1] += 1
        if c in bucket2[t]:
            imos[t-1] -= 1
        else:
            imos[t] -= 1

ans = tmp = 0
for im in imos:
    tmp += im
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

N,C = li()
MAX = 10**5

stc = []
for _ in range(N):
    stc.append(list(li()))
    
rec = [[0 for _ in range(MAX+1)] for _ in range(C)]
for s,t,c in stc:
    rec[c-1][s-1] += 1
    rec[c-1][t] -= 1
    
for i in range(C):
    rec[i] = list(accumulate(rec[i]))
    rec[i] = [min(1,reci) for reci in rec[i]]
    
rec_total = rec[0]
    
for i in range(1,C):
    for j in range(MAX+1):
        rec_total[j] = rec_total[j] + rec[i][j]

print(max(rec_total))

Submission status: Accepted

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

db = [0 for i in range(100001)]
mem = [set() for i in range(C + 1)]

for i in range(N):
    s, t, c = map(int, input().split())
    if s not in mem[c]:
        db[s - 1] += 1
        mem[c].add(s)
    else:
        db[s] += 1
    
    if t not in mem[c]:
        db[t] -= 1
        mem[c].add(t)
    else:
        db[t - 1] -= 1

ans = 1
cnt = 0
for d in db:
    cnt += d
    ans = max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
T_MAX = 10**5
n, nc = list(map(int, input().split()))
stc = [list(map(int, input().split())) for _ in range(n)]

recs = [[0]*(T_MAX+1) for c in range(nc+1)]
for s, t, c in stc:
    recs[c][s-1:t] = [1]*(t-s+1)

ans = max(map(sum, zip(*recs)))
print(ans)

Submission status: Accepted

Solution code:
N, c = map(int, input().split())
time = [0 for i in range(100001)]
time_c = [[0 for i in range(100001)] for j in range(c)]
          
for i in range(N):
    S, T, C = map(int, input().split())
    time_c[C - 1][S] += 1
    time_c[C - 1][T] -= 1
    
for i in range(100001):
    for j in range(c):
        if time_c[j][i] > 0:
            time[i - 1] += time_c[j][i]
        if time_c[j][i] < 0:
            time[i] += time_c[j][i]

for i in range(1, 100001):
    time[i] += time[i - 1]

print(max(time))

Submission status: Accepted

Solution code:
f = lambda: map(int, input().split())
n,c = f()
d = [list(f()) for _ in range(n)]
d.sort(key=lambda x: (x[2],x[0]))
p = []
for i in range(n):
    if len(p)>0 and p[-1][2]==d[i][2] and p[-1][1]==d[i][0]:
        p[-1][1]=d[i][1]
    else:
        p.append(d[i])
ans = [0]*200100
for i in range(len(p)):
    ans[p[i][0] - 1] += 1
    ans[p[i][1]] -= 1
from itertools import accumulate as acc
print(max(acc(ans)))

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
T = [[0 for k in range(100001)] for l in range(C)]

for k in range(N):
    s, t, c = map(int, input().split())
    T[c-1][s-1] += 1
    T[c-1][t] -= 1
for l in range(C):
    for k in range(1,100001):
        T[l][k] += T[l][k-1]

ans = 0
for k in range(100001):
    t = 0
    for l in range(C):
        if T[l][k] >= 1:
            t += 1
    ans = max(ans, t)

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

def unite_intervals(lst: list) -> list:

    # 終点の最大値の分だけ配列を確保(0-indexed)
    n = len(lst)
    mx = max([lst[i][1] for i in range(n)])
    imos = [0] * (2*(mx+1) + 2)
    
    # 始点を+1, 終点を-1する
    for st, ed in lst:
        imos[2*st + 1] += 1
        imos[2*ed] -= 1
        
    imos_cum = list(accumulate(imos))

    # 総合的な[start, last)区間を答えに詰めていく
    ans = []
    start = -1
    last = -1
    for i in range(mx+2):
        if imos_cum[2*i] == 0 and imos_cum[2*i+1] > 0:
            start = i
            
        elif imos_cum[2*i+1] > 0 and imos_cum[2*i+2] == 0:
            last = i+1
            
            ans.append((start, last))
            start = -1
            last = -1
        
    return ans

import sys
sdin = sys.stdin.readline

n,c = map(int, sdin().split())

dic = {}  
for i in range(c):
    dic.update({i+1: []})
    
# 各チャンネルの録画時刻を記録
ch_st = []
max_t = 0
for _ in range(n):
    s,t,ch = map(int, sdin().split())
    max_t = max(max_t, t)
    dic[ch].append((max(0,s-1),t))
    
# 被っている部分をマージする
for ch in range(c):
    ch += 1
    if len(dic[ch]) > 0:
        dic[ch] = unite_intervals(dic[ch])
    
# imos法で
imos = [0]*(max_t+1)
for ch in range(1,c+1):
    for s, t in dic[ch]:
        imos[s] += 1
        imos[t] -= 1
        
imos = list(accumulate(imos))
print(max(imos))

Submission status: Accepted

Solution code:
from itertools import accumulate as ac
from operator import add
n,C=map(int,input().split())
d=[[0 for _ in range(200002)] for _ in range(C)]
for _ in range(n):
  s,t,c=map(int,input().split())
  d[c-1][s*2-1]+=1
  d[c-1][t*2+1]-=1
o=[[1 if i else 0 for i in ac(i)] for i in d]
*v,=map(lambda *x:sum(x),*o)
print(max(v))

Submission status: Accepted

Solution code:
def d_recording(N, C, R):
    # N:録画する番組の数
    # C:テレビが受信できるチャンネルの数
    # R:録画する番組の情報 [開始時刻s,終了時刻t,チャンネルc]
    from itertools import accumulate

    # いつまで録画機を動かすか。終了時刻の最大値10**5, 単位時間を0.5とするので*2
    # 時刻を0からスタートさせるので+1, 累積和のために+1
    l = 10**5 * 2 + 2
    running_recorder = [0] * l  # [k]:ある時刻に動作中の録画機の数

    for channel in range(1, C + 1):
        rec = [0] * l  # [k]:チャンネルkを録画しているか否か
        # 累積和を取る
        for s, t, c in R:
            if c == channel:
                # 録画開始時刻の0.5前を+1,終了時刻を-1
                # (終了時刻は含まないという録画機の条件より、このようにする)
                rec[s * 2 - 1] += 1
                rec[t * 2] -= 1
        rec = accumulate(rec)
        # あるチャンネルを録画している時間帯では、録画機を1個使わねばならない
        for j, running in enumerate(rec):
            if running > 0:
                running_recorder[j] += 1
    ans = max(running_recorder)
    return ans

N, C = [int(i) for i in input().split()]
R = [[int(i) for i in input().split()] for j in range(N)]
print(d_recording(N, C, R))

Submission status: Accepted

Solution code:
def d_recording(N, C, R):
    # N:録画する番組の数
    # C:テレビが受信できるチャンネルの数
    # R:録画する番組の情報 [開始時刻s,終了時刻t,チャンネルc]
    from itertools import accumulate
    start = [row[0] for row in R]
    end = [row[1] for row in R]
    channel_num = [row[2] for row in R]

    # いつまで録画機を動かすか。0.5を単位時間とするので*2
    # 時刻を0からスタートさせるので+2
    l = max(end) * 2 + 2
    running_recorder = [0 for _ in range(l)]  # [k]:ある時刻に動作中の録画機の数

    for channel in range(1, C + 1):
        rec = [0 for _ in range(l)]  # [k]:チャンネルkを録画しているか否か
        # 累積和を取る
        for s, t, c in zip(start, end, channel_num):
            if c == channel:
                # 録画開始時刻の0.5前を+1,終了時刻を-1
                # (終了時刻は含まないという録画機の条件より、このようにする)
                rec[s * 2 - 1] += 1
                rec[t * 2] -= 1
        rec = accumulate(rec)
        # あるチャンネルを録画している時間帯では、録画機を1個使わねばならない
        for j, running in enumerate(rec):
            if running > 0:
                running_recorder[j] += 1
    ans = max(running_recorder)
    return ans

N, C = [int(i) for i in input().split()]
R = [[int(i) for i in input().split()] for j in range(N)]
print(d_recording(N, C, R))

Submission status: Accepted

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


# --------------------------------------------

dp = None


def main():
    N, C = li_input()

    A = [[0] * 100001 for _ in range(C)]
    S = [0] * 100001

    for i in range(N):
        s, t, c = li_input()

        for j in range(s - 1, t):
            A[c - 1][j] += 1

    for a in A:
        for i in range(1, len(a)):
            if a[i]:
                S[i] += 1

    print(max(S))


main()

Submission status: Accepted

Solution code:
import functools
N, C = map(int, input().split())
P = [[0 for c in range(C)] for i in range(10 ** 5 + 1)]
T = 0
for i in range(N):
  s, t, c = map(int, input().split())
  T = max(t, T)
  for j in range(s - 1, t):
    P[j][c - 1] = 1
ans = 0
for p in P[:T + 1]:
  ans = max(sum(p), ans)
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

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

T = 10 ** 5 + 1
A = [[0] * T for _ in range(C)]
for _ in range(N):
    s, t, c = map(int, input().split())
    A[c - 1][s - 1:t] = [1] * (t - s + 1)

ans = 0
for j in range(1, T):
    cnt = 0
    for i in range(C):
        cnt += A[i][j]
    ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

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

T = 10 ** 5 + 1
A = [[0] * T for _ in range(C)]
for _ in range(N):
    s, t, c = map(int, input().split())
    A[c - 1][s] += 1
    A[c - 1][t] -= 1

for i in range(C):
    for j in range(1, T):
        A[i][j] += A[i][j - 1]
        if A[i][j] == 1 and A[i][j - 1] == 0:
            A[i][j - 1] = 1

ans = 0
for j in range(1, T):
    cnt = 0
    for i in range(C):
        cnt += A[i][j]
    ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


# --------------------------------------------

dp = None


def main():
    N, C = li_input()

    A = [[0] * 100001 for _ in range(C)]
    S = [0] * 100001

    for i in range(N):
        s, t, c = li_input()

        for j in range(s, t):
            A[c - 1][j] += 1

    for a in A:
        for i in range(1, len(a)):
            if a[i] == 1 or (i != len(a) - 1 and a[i + 1]) == 1:
                S[i] += 1

    print(max(S))


main()

Submission status: Accepted

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

n, c = map(int, sdin().split())
stc = []
for _ in range(n):
    stc.append(tuple(map(int, sdin().split())))
    
table = [[0]*(10**5) for _ in range(c)]

for s,t,c in stc:
    table[c-1][s-1:t] = [1]*(t-s+1)
    
ans = max(map(sum, zip(*table)))
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,C = inpl()
datas = [[] for i in range(C)]
Times = set()
for _ in range(N):
	s,t,n = inpl()
	datas[n-1].append([s,t])
	Times.add(s-0.5)
	Times.add(t)

dataset = []
for c in range(C):
	data = sorted(datas[c])
	if len(data) == 0: continue
	bs,bt = data[0]
	for i in range(1,len(data)):
		s,t = data[i]
		if bt == s:
			#Times.remove(s-0.5)
			s = bs
		else:
			dataset.append([bs-0.5,bt])
		bs,bt = s,t
	dataset.append([bs-0.5,bt])

ddT = defaultdict(int)
for i,t in enumerate(sorted(list(Times))):
	ddT[t] = i
	
L = len(Times)
imos = [0]*L
for s,t in dataset:
	s,t = ddT[s],ddT[t]
	imos[s] += 1
	imos[t] -= 1

tmp = 0
ans = 0
for i in range(L):
	tmp += imos[i]
	ans = max(tmp,ans)

print(ans)

Submission status: Accepted

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

arr = [[0 for i in range(c)] for j in range(10**5+1)]

for i in range(n):
	s,t,ch = map(int,raw_input().split())
	s -= 1
	ch -= 1
	for i in range(s,t):
		arr[i][ch] = 1

ans = 0

for i in range(10**5+1):
	ans = max(ans,sum(arr[i]))

print ans

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 

ans = 0
for i in range(100000):
    if sum(r[i]) > ans:
        ans = sum(r[i]) 

print(ans)

Submission status: Accepted

Solution code:
n,C = map(int,input().split())
d = [[0]*C for i in range(10**5)]

for i in range(n):
    s,t,c = map(int,input().split())
    for j in range(s-1,t):
        d[j][c-1] = 1

#print(d)

a = 1
for i in range(10**5):
    s = sum(d[i])
    if s > a:
        a = s

print(a)

Submission status: Accepted

Solution code:
N,C=map(int,input().split())
s=[0 for i in range(N)];t=[0 for i in range(N)];c=[0 for i in range(N)]
MT=0
for i in range(N):
    s[i],t[i],c[i]=map(int,input().split())
    s[i]-=1
    t[i]-=1
    c[i]-=1
for i in range(N):
    if t[i]>MT:
        MT=t[i]
CBC=[[0 for i in range(MT+1)] for i in range(C)]
for i in range(N):
    for j in range(s[i]-1,t[i]):
        CBC[c[i]][j]=1
MaxC=0
for i in range(MT+1):
    NowC=0
    for j in range(C):
        if CBC[j][i]==1:
            NowC+=1
    if NowC>MaxC:
        MaxC=NowC
print(MaxC)

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
r = [[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):
        r[i][c - 1] = 1
ans = 0
for t in r:
    sum_t = sum(t)
    if sum_t > ans:
        ans = sum_t

print(ans)

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 operator
N, C = map(int, input().split())
stc = [[int(x) for x in input().split()] for _ in range(N)]

united = []
pc,ps,pt = 0,0,0
for x in sorted(stc, key=operator.itemgetter(2,0,1)):
    s, t, c = x
    if c == pc and s == pt:
        united[-1][1] = t
    else:
        united.append([s, t, c])
    ps, pt, pc = x
cnt = [0] * (10**5 + 1)
for x in united:
    s,t,c = x
    for i in range(s - 1, t):
        cnt[i] += 1
print(max(cnt))

Submission status: Accepted

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

im = [[0] * (10**5 + 1) for _ in range(C + 1)]
for x in stc:
    s,t,c = x
    im[c][s] += 1
    im[c][t] -= 1

for c in range(1, C + 1):
    v = 0
    for i in range(1, 10**5 + 1):
        n = im[c][i]
        v += n
        if n > 0:
            im[c][i - 1] += 1
        im[c][i] = v
print(max([sum(x) for x in zip(*im[1:])]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, C, STC):
    tbl = [0] * (2*int(1e+5) + 2)
    ST = defaultdict(list)
    for s, t, c in STC:
        ST[c].append((s, t))
    for st in ST.values():
        st.sort()
        for i, (s, t) in enumerate(st):
            if i > 0 and st[i-1][1] == st[i][0]:
                tbl[2*(st[i][0])] += 1
                tbl[2*(st[i][1])] -= 1
            else:
                tbl[2*st[i][0]-1] += 1
                tbl[2*st[i][1]] -= 1

    for i in range(1, len(tbl)):
        tbl[i] += tbl[i-1]
    ans = max(tbl)
    return ans


def main():
    N, C = read_int_n()
    STC = [read_int_n() for _ in range(N)]
    print(slv(N, C, STC))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
programs = [[0 for _ in range(C)] for _ in range(10**5)]
for _ in range(N):
    s, t, c = map(int, input().split())
    for i in range(s-1, t):
        programs[i][c-1] = 1
ret = 0
for i in range(10**5):
    ret = max(ret, sum(programs[i]))
print(ret)

Submission status: Accepted

Solution code:
import functools
N, C = map(int, input().split())
T = [[0 for i in range(10 ** 5 + 1)] for j in range(C)]
for i in range(N):
  s, t, c = map(int, input().split())
  for j in range(s - 1, t):
    T[c - 1][j] = 1
ans = 0
for j in range(10 ** 5 + 1):
  r = 0
  for i in range(C):
    r += T[i][j]
  ans = max(ans, r)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n, C = map(int, input().split())
lst = [[0] * 100002 for _ in range(C)]
end = []
for _ in range(n):
  s, t, c = map(int, input().split())
  c -= 1
  lst[c][s] += 1
  lst[c][t + 1] -= 1

for c in range(C):
  lst[c] = list(itertools.accumulate(lst[c]))
  for i in range(100002):
    if lst[c][i] >= 2:
      lst[c][i] = 1

ans = 0
for i in range(100002):
  tmp = 0
  for c in range(C):
    tmp += lst[c][i]
  ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
N,C = map(int,input().split())
tvs = [list(map(int,input().split())) for _ in range(N)]
chans = [[] for _ in range(C+1)]
tvs.sort(key=lambda x:x[0])
targets = []
times = [0]*(pow(10,5)+2)

for tv in tvs:
  chans[tv[2]].append([tv[0],tv[1]])

for chan in chans:
  tmp = []
  if len(chan) == 1:
    targets.append(chan[0])
    continue
  for x in range(len(chan)):
    if len(tmp) == 0:
      tmp = chan[x]
      continue
    if chan[x][0] <= tmp[1] + 1:
      tmp[1] = chan[x][1]
      if x == len(chan)-1:
        targets.append(tmp)
    else:
      targets.append(tmp)
      tmp = chan[x]

for target in targets:
  times[target[0]] += 1
  times[target[1]+1] += -1

for j in range(1,pow(10,5)+2):
  times[j] += times[j-1]

print(max(times))