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:
N, C = map(int, input().split())
table = [[0]*100000 for i in range(C)]

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

print(max(map(sum, zip(*table))))

Submission status: Accepted

Solution code:
import heapq

N, C = map(int, input().split())
TVs = [[] for i in range(C)]
for i in range(N):
    s, t, ch = map(int, input().split())
    TVs[ch - 1].append((s, t))

pq = []
for ch, TVc in enumerate(TVs):
    if not TVc: continue
    TVc.sort()
    heapq.heappush(pq, (TVc[0][0] - 0.5, ch))

states = [0] * C
iTVs = [0] * C

prev = 0
ans = 0
while pq:
    tm, ch = heapq.heappop(pq)
    if tm != prev:
        ans = max(ans, sum(states))
        prev = tm

    if states[ch] == 0:
        # チャンネルchの番組録画を、時刻tmから開始
        states[ch] = 1
        heapq.heappush(pq, (TVs[ch][iTVs[ch]][1], ch)) # 終了時刻をpqに追加
    else:
        # チャンネルchの番組録画を、時刻tmで終了
        states[ch] = 0
        iTVs[ch] += 1
        if iTVs[ch] >= len(TVs[ch]): continue

        if tm == TVs[ch][iTVs[ch]][0]:
            # 録画範囲が連続しているならば、次の番組録画を開始
            states[ch] = 1
            heapq.heappush(pq, (TVs[ch][iTVs[ch]][1], ch)) # 終了時刻をpqに追加
        else:
            heapq.heappush(pq, (TVs[ch][iTVs[ch]][0] - 0.5, ch)) # 次の開始時刻をpqに追加

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


def main():
    N, C = list(map(int, input().split()))

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

    ans = [0] * (2 * 10 ** 5 + 2)
    for i in range(1, C + 1):
        dp = [0] * (2 * 10 ** 5 + 2)

        for s, t, c in s_t_c:
            if c == i:
                dp[s * 2 - 1] += 1
                dp[t * 2] -= 1
        for j in range(1, len(dp)):
            dp[j] += dp[j - 1]

        for j in range(len(dp)):
            ans[j] += dp[j] > 0

    print(max(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

# arr[col] には、区間の始まり ==> 1,区間中 ==> 0,区間終わり ==> -1
# 連続した区間は結合した形で表現される

arr = [[0]*L for _ in range(c)]

for i in range(n):
    s,t,col = map(int,input().split(" "))
    arr[col-1][s-1] += 1
    arr[col-1][t-1] -= 1

imos = [0]*L

#全チャンネルを同時に考えたいもす法
for i in range(c):
    for p in range(L):
        if arr[i][p] == 1: imos[p] += 1    
        if arr[i][p] == -1: imos[p+1] -= 1


#累積和をとれば、区間内の最大のrec数は値のmax.
ans = 0
for i in range(1,L):
    imos[i] += imos[i-1]
    ans = max(ans, imos[i])

print(ans)

Submission status: Accepted

Solution code:
n, _ = map(int, input().split())
a = sorted(tuple(map(int, input().split())) for _ in range(n))
r = [(0,0)]
for s, t, c in a:
    u, i = min((u+0.5*(c!=d), i) for i, (u, d) in enumerate(r))
    if s < u:
        r.append((t, c))
    else:
        r[i] = (t, c)
print(len(r))

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import accumulate

n, v = map(int, input().split())
programs = defaultdict(list)
for _ in range(n):
    s, t, c = map(int, input().split())
    programs[c].append((s, t))

imos = [0] * (10 ** 5 + 2)
for c, p in programs.items():
    p.sort()
    ps, pt = p[0]
    for s, t in p[1:]:
        if pt == s:
            pt = t
        else:
            imos[ps - 1] += 1
            imos[pt] -= 1
            ps, pt = s, t
    imos[ps - 1] += 1
    imos[pt] -= 1

print(max(accumulate(imos)))

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import accumulate

n, v = map(int, input().split())
programs = defaultdict(list)
for _ in range(n):
    s, t, c = map(int, input().split())
    programs[c].append((s, t))

imos = [0] * (2 * 10 ** 5 + 2)
for c, p in programs.items():
    p.sort()
    ps, pt = p[0]
    for s, t in p[1:]:
        if pt == s:
            pt = t
        else:
            imos[2 * ps - 1] += 1
            imos[2 * pt + 1] -= 1
            ps, pt = s, t
    imos[2 * ps - 1] += 1
    imos[2 * pt + 1] -= 1

print(max(accumulate(imos)))

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heapreplace, heappush

n, v = map(int, input().split())
programs = defaultdict(list)
for _ in range(n):
    s, t, c = map(int, input().split())
    programs[c].append((s, t))

combined = []
for c, p in programs.items():
    p.sort()
    ps, pt = p[0]
    for s, t in p[1:]:
        if pt == s:
            pt = t
        else:
            combined.append((ps, pt, c))
            ps, pt = s, t
    combined.append((ps, pt, c))
combined.sort()

recorders = [(-1, None)]
for s, t, c in combined:
    end, channel = recorders[0]
    if end < s or c == channel:
        heapreplace(recorders, (t, c))
    else:
        heappush(recorders, (t, c))
print(len(recorders))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
N, C = map(int, input().split())
table = [[0] * C for i in range(10 ** 5 + 1)]
for i in range(N):
    s, t, c = map(int, input().split())
    table[s - 1][c - 1] += 1
    table[t - 1][c - 1] -= 1

imos = [0] * (10 ** 5 + 1)
for i in range(10 ** 5 + 1):
    for j in range(C):
        if table[i][j] == 1:
            imos[i] += 1
        if table[i][j] == -1:
            imos[i + 1] -= 1

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

import numpy as np

N, C = map(int, input().split(' '))
s = []
t = []
c = []
for i in range(N):
    s_i, t_i, c_i = map(int, input().split(' '))
    s.append(s_i)
    t.append(t_i)
    c.append(c_i - 1)
T = 2*max(t)
# for i in range(N):
#     table[2*s[i]-1: 2*t[i]] += 1
table = np.zeros(T)
for i in range(C):
    table_i = np.zeros(T)
    for j in range(N):
        if c[j] == i:
            table_i[2*s[j]-1: 2*t[j]] = 1
    table += table_i
print(int(np.max(table)))

Submission status: Accepted

Solution code:
from heapq import heapreplace, heappush

n, v = map(int, input().split())
programs = [tuple(map(int, input().split())) for _ in range(n)]
programs.sort()
tmp = [None] * v
combined = []
for s, t, c in programs:
    c -= 1
    prev = tmp[c]
    if prev is not None:
        ps, pt, pc = prev
        if pt == s:
            tmp[c] = (ps, t, c)
        else:
            combined.append((ps, pt, pc))
            tmp[c] = (s, t, c)
    else:
        tmp[c] = (s, t, c)
for prev in tmp:
    if prev is not None:
        combined.append(prev)
combined.sort()

recorders = [(-1, None)]
for s, t, c in combined:
    end, channel = recorders[0]
    if end < s or c == channel:
        heapreplace(recorders, (t, c))
    else:
        heappush(recorders, (t, c))
print(len(recorders))

Submission status: Accepted

Solution code:
N,C=list(map(int,input().split()))
A=[list(map(int,input().split())) for _ in range(N)]
T=0
for i in A:
    T=max(i[1],T)
timelist=[0 for _ in range((T)*2)]
ch=[[] for _ in range(C)]
for item in A:
    ch[item[2]-1].append(item)


count=0
for channel in ch:
    count+=1
    for item in channel:
        starttime=item[0]
        endtime=item[1]
        for time in range(starttime*2-2,endtime*2-2,2):
            timelist[time]+=1
            if(timelist[time]>count):
                timelist[time]=count
            timelist[time+1]+=1
            if(timelist[time+1]>count):
                timelist[time+1]=count
        timelist[time+2]+=1
        if(timelist[time+2]>count):
                timelist[time+2]=count
print  (max (timelist))

Submission status: Accepted

Solution code:
L = 100005

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

arr = [[0]*L for j in range(c)]
for _ in range(n):
    s,t,col = map(lambda x:int(x)-1, input().split())
    arr[col][s] += 1
    arr[col][t] -= 1

imos = [0]*L

for i in range(c):
    for p in range(L):
        if arr[i][p] == 1: imos[p] += 1
        if arr[i][p] == -1: imos[p+1] -= 1

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

print(ans)

Submission status: Accepted

Solution code:
n, c = list(map(int, input().split()))
tv = []
for i in range(n):
    x, y, z = list(map(int, input().split()))
    tv.append([x, y, z])
channels = [[0 for _ in range(max(tv, key=lambda lst: lst[1])[1] + 1)] for _ in range(c + 1)]
for program in tv:
    start = program[0]
    end = program[1]
    channel = program[2]
    for time in range(start, end+1):
        channels[channel][time] = 1
res = 0
for time in range(len(channels[0])):
    now = 0
    for channel in range(c+1):
        now += channels[channel][time]
    if res < now:
        res = now
print(res)

Submission status: Accepted

Solution code:
def main():
    n,cc=[int(i) for i in input().split()]
    rec=[]
    for i in range(n):
        s,t,c=[int(k) for k in input().split()]
        rec.append([float(s),float(t),c])
    slot=[[float(-1),-1] for i in range(cc)]
    rec.sort(key=lambda rec:rec[0])
    for r in rec:
        for k,s in enumerate(slot):
            tmp=0
            if s[1]!=r[2]:
                #チャンネルが違う
                tmp=r[0]
                r[0]=r[0]-0.5
            if s[0]<=r[0]:
                s[0]=r[1]
                s[1]=r[2]
                break
            r[0]=tmp
    print(len([i for i in slot if i[0]!=-1 and i[1]!=-1]))

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

import numpy as np

nc = raw_input()
nc = nc.split()
n,c = map(int,nc)

tt = np.zeros([(10**5),c],int)

for i in range(n):
    stc = raw_input()
    stc = stc.split()
    s,t,c = map(int,stc)
    j = s
    while j <= t:
        tt[j-1][c-1] = 1
        j += 1

ans = np.max(np.sum(tt, axis=1))

print ans

Submission status: Accepted

Solution code:
from heapq import heappop as pop, heappush as push

peak, curr = 0, 0

stuff = []
n, c = map(int, raw_input().split())
for _ in xrange(n):
  stuff.append(map(float, raw_input().split()))
  stuff[-1][-1] = int(stuff[-1][-1]) - 1
  
stuff = sorted(stuff)
has_camera = [False] * c
last_ending = [-1] * c
ending = []
for st, end, ch in stuff:
  while ending and ending[0][0] <= st - 0.5:
    cend, cch = pop(ending)
    if last_ending[cch] == cend:
        has_camera[cch] = False
        curr -= 1
  if not has_camera[ch]:
    has_camera[ch] = True
    curr += 1
  push(ending, (end, ch))
  last_ending[ch] = end
  peak = max(peak, curr)
  
print peak

Submission status: Accepted

Solution code:
def inpl(): return tuple(map(int, input().split()))

N, C = inpl()
P = sorted([inpl() for _ in range(N)])

R = [[[-1, 0, -1]] for _ in range(30)]
for s, t, c in P:
    i = 0
    # 連続録画を探す
    sr = [i for i in range(30) if R[i][-1][2] == c and R[i][-1][1] <= s]
    if sr:
        R[min(sr)].append([s, t, c])
    else:
        r = [i for i in range(30) if R[i][-1][1] <= s - 0.5]
        R[min(r)].append([s, t, c])

for i in range(30):
    if len(R[i]) == 1:
        print(i)
        break
else:
    print(30)

Submission status: Accepted

Solution code:
N,C=map(int,input().split())
channel=[tuple(map(int,input().split())) for i in range(N)]
channel=sorted(channel,key=lambda cha: cha[0])

n=0
while(channel!=[]):
    c=[]
    n+=1
    pro=channel[0]
    channel.remove(pro)
    for i in channel:
        if i[0]>pro[1]:
            pro=i
        elif(i[0]==pro[1] and i[2]==pro[2]):
            pro=i
        else:
            c.append(i)
    channel=c
print(n)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

def solve():
    n, c = map(int, input().split())
    c_info = [[int(i) for i in input().split()] for _ in range(n)]
    c_info.sort(key=lambda x: (x[2], x[0]))
    info = []
    cnt = 0
    
    while cnt < n:
        if cnt == n - 1:
            info.append(c_info[cnt])
            break
        if c_info[cnt][1] == c_info[cnt + 1][0] and c_info[cnt][2] == c_info[cnt + 1][2]:
            tc = c_info[cnt][2]
            t = [c_info[cnt][0], c_info[cnt + 1][1], tc]
            cnt += 1
            while cnt < n - 1 and t[1] == c_info[cnt + 1][0] and tc == c_info[cnt + 1][2]:
                t = [t[0], c_info[cnt + 1][1], tc]
                cnt += 1
            info.append(t)
            if cnt == n - 1:
                break
        else:
            info.append(c_info[cnt])
        cnt += 1

    tarr = [0] * (2 + 10 ** 5)
    for elem in info:
       tarr[elem[0]] += 1
       tarr[elem[1] + 1] -= 1
    
    ans = 1
    tans = 0
    for elem in tarr:
        tans += elem
        ans = max(ans, tans)
    print(ans)

if __name__=="__main__":
    solve()

Submission status: Accepted

Solution code:
st=input().split()
N=int(st[0]);C=int(st[1])
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):
    st=input().split()
    s[i]=int(st[0])-1;t[i]=int(st[1])-1;c[i]=int(st[2])-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())
ps = [[] for i in range(C)]
for i in range(N):
    s,t,c = map(int,input().split())
    ps[c-1].append((s,t))

MAX_N = 10**5+3
imos = [0] * MAX_N
for c in range(C):
    ps[c].sort()
    cont = False
    for i,(s,t) in enumerate(ps[c]):
        if not cont:
            imos[s-1] += 1
        if i < len(ps[c])-1 and t == ps[c][i+1][0]:
            cont = True
        else:
            imos[t] -= 1
            cont = False

ans = t = 0
for a in imos:
    t += a
    ans = max(ans, t)
print(ans)

Submission status: Accepted

Solution code:
[n, c] = map(int, raw_input().split())
cs = [None] * c
for i in range(c):
    cs[i] = list()
for i in range(n):
    [s, t, ci] = map(int, raw_input().split())
    cs[ci - 1].append((s, t))
starts = []
ends = []
for i in range(c):
    if len(cs[i]) == 0: continue
    cs[i].sort()
    j = 0
    k = 0
    while j + k < len(cs[i]) - 1:
        a = cs[i][j+k][1]
        b = cs[i][j+k+1][0]
        if a == b:
            k += 1
        else:
            start = cs[i][j][0]
            end = cs[i][j+k][1]
            starts.append(start)
            ends.append(end)
            j += k + 1
            k = 0
    start = cs[i][j][0]
    end = cs[i][j+k][1]
    starts.append(start)
    ends.append(end)
starts.sort()
ends.sort()
i = 0
j = 0
d = 0
while i < len(starts) and j < len(ends):
    if starts[i] < ends[j]:
        i += 1
    elif starts[i] == ends[j]:
        i += 1
    else:
        j += 1
    d = max(d, i - j)
print d

Submission status: Accepted

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

su = [0]*(10**5+1)
Q = [[] for i in range(C)]
for i in range(N):
    s, t, c = map(int, input().split())
    Q[c-1].append([s, t])
R = [[] for i in range(C)]
for i in range(C):
    q = Q[i]; q.sort()
    r = R[i]
    if len(q) == 0:
        continue
    r.append(q[0])
    for j in range(1, len(q)):
        if r[-1][1] == q[j][0]:
            r[-1][1] = q[j][1]
        else:
            r.append(q[j])
    for a, b in r:
        su[a-1] += 1
        su[b] -= 1
ans = 0; tmp = 0
for i in range(10**5+1):
    tmp += su[i]
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n, c = map(int, raw_input().split())
l = deque()
for _ in xrange(n):
    s, t, c = map(int, raw_input().split())
    l.append((s, t, c))
def comp(t1, t2):
    if t1[0] == t2[0]:
        return cmp(t1[1], t2[1])
    return cmp(t1[0], t2[0])
l, cnt, rec = sorted(l, cmp = comp), 0, deque()
for s, t, c in l:
    f = False
    for i, (rt, rc) in enumerate(rec):
        if c == rc:
            if s >= rt:
                rec[i] = (t, c)
                f = True
                break
        else:
            if s > rt:
                rec[i] = (t, rc)
                f = True
                break
    if not f:
        rec.append((t, c))
print len(rec)

Submission status: Accepted

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

r = [[0 for i in range(C)] for j in range(100000)]
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 i in range(100000):
    val = sum(r[i])
    if val > ans:
        ans = val

print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n, cc = map(int, input().split())
    channels = [[] for _ in range(cc)]
    for i in range(n):
        s, t, c = map(int, input().split())
        c -= 1
        channels[c].append((s, t))
    for i in range(cc):
        channels[i].sort()
        merged_program = []
        for program in channels[i]:
            if not merged_program:
                merged_program.append(program)
            elif merged_program[-1][1] == program[0]:
                merged_program[-1] = (merged_program[-1][0], program[1])
            else:
                merged_program.append(program)
        channels[i] = merged_program
    events = []
    for programs in channels:
        for s, t in programs:
            events.append((s * 2 - 1, +1))
            events.append((t * 2, -1))
    events.sort()
    ans = 0
    cnt = 0
    for ti, ty in events:
        cnt += ty
        ans = max(ans, cnt)
    print(ans)

Submission status: Accepted

Solution code:
N,C = map(int, raw_input().split())
T = [[] for _ in range(C)]
for _ in range(N):
  s,t,c = map(int, raw_input().split())
  T[c-1] += [(s,t)]
for t in T:
  t.sort()
D = [0]*(10**5+1)
for t in T:
  if len(t)>0:
    D[t[0][0]-1] += 1
    for i in range(len(t)-1):
      if t[i][1]<t[i+1][0]:
        D[t[i][1]] -= 1
        D[t[i+1][0]-1] += 1
    D[t[-1][1]] -=1
ans = 0
a = 0
for d in D:
  a += d
  ans = max(ans, a)
print ans

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n, c = na()
stc = []
for i in range(n):
    stc.append(na())
stc.sort(key=lambda x: (x[2], x[0]))

nstc = []
for i in range(n):
    if len(nstc) > 0 and nstc[-1][2] == stc[i][2] and nstc[-1][1] == stc[i][0]:
        nstc[-1][1] = stc[i][1]
    else:
        nstc.append(stc[i])
n = len(nstc)

h = [0]*200005
for i in range(n):
    h[2*nstc[i][0] - 1] += 1
    h[2*nstc[i][1]] += -1
for i in range(len(h)-1):
    h[i] += h[i-1]
print(max(h))

Submission status: Runtime Error

Solution code:
def Recording():
    n, c = map(int, input().split())
    num = 30#2*10**5+1 

    # チャンネルごとにimos配列
    imos = [[0]*num for _ in range(c)]
    
    # imos
    for _ in range(n):
        s, t, c0 = map(int, input().split())
        if imos[c0-1][s*2] < 0 and imos[c0-1][t*2-1] > 0:
            imos[c0-1][s*2] = 0
            imos[c0-1][t*2-1] = 0
        elif imos[c0-1][s*2] < 0:            
            imos[c0-1][s*2] = 0
            imos[c0-1][t*2-1] += 1
        elif imos[c0-1][t*2-1] > 0:    
            imos[c0-1][s*2-1] += 1
            imos[c0-1][t*2-1] = 0
        else:
            imos[c0-1][s*2-1] += 1
            imos[c0-1][t*2] -= 1
    ans = [0 for _ in range(num)]
    for i in range(c):
        for j in range(1, num):
            imos[i][j] += imos[i][j-1]
            ans[j] += imos[i][j]
    print(max(ans))
    
if __name__ == '__main__':
    Recording()

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
from operator import itemgetter
#from heapq import heappush, heappop
#import numpy as np
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

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

for i in range(len(ans)-1):
    ans[i+1] += ans[i]
print(min(max(ans)), C)

Submission status: Runtime Error

Solution code:
n, C = map(int, input().split())
cq = [[] for _ in range(C)]

for _ in range(n):
    s, t, c = tuple(map(int, input().split()))
    if cq[c-1]:
        fs, ft = cq[c-1][-1]
        if ft != s:
            cq[c-1].append([s, t])
        else:
            cq[c-1][-1] = [fs, t]
    else:
        cq[c-1].append([s, t])

R = [0] * (2*10**5+1)
for qq in cq:
    for s, t in qq:
        R[2*s-1] += 1
        R[2*t+1] -= 1

from itertools import accumulate
CR = list(accumulate(R))

print(max(CR))

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
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.array([])
for e in stc:
  w=e[1]-e[0]
  cht.vstack((cht,np.pad(np.ones(2*(e[1]-e[0])+1),(2*e[0]-1,m-2*e[1]),\
                mode='constant',constant_values=(1,1))))
mnr=0
for i in range(1,m+1):
  mnr=max(mnr,sum(cht[ch][i] for ch in range(c)))
print(mnr)

Submission status: Runtime Error

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

N,C = MI()
A = [[0]*(10**5+1) 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]))

# A[i][j] が正 ⇔ チャンネル i が時刻 j に録画機が必要

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

print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

N, C = map(int,input().split())
Mx = 100#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))

Submission status: Runtime Error

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

N, C = map(int,input().split())
Mx = 10**5
sch = [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 p in plist:
    if len(p)==0:
        continue
    p.sort()
    prevt = -1
    for s, t in p:
        if prevt == s:
            sch[prevt] += 1
        else:
            sch[s-1] += 1
        sch[t] -= 1
        prevt = t

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

print(max(sch))

Submission status: Runtime Error

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

N, C = map(int,input().split())
Mx = 10**5+1
sch = [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 p in plist:
    if len(p)==0:
        continue
    p.sort()
    prevt = 0
    for s, t in p:
        sch[s] += 1
        sch[t+1] -= 1
        if prevt == s:
            sch[prevt+1] += 1
            sch[s] -= 1
        prevt = t

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

print(max(sch))

Submission status: Runtime Error

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

N, C = map(int,input().split())
Mx = 10**5+1
sch = [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 p in plist:
    p.sort()
    prevt = 0
    for s, t in p:
        sch[s] += 1
        sch[t+1] -= 1
        if prevt == s:
            sch[prevt+1] += 1
            sch[s] -= 1
        prevt = t
for i in range(1,Mx):
    sch[i]+=sch[i-1]
print(max(sch))

Submission status: Runtime Error

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000000)
N, C = map(int, input().split())
record = [[0 for _ in range(10 ** 5)] for _ in range(C)]
for _ in range(N):
    s, t, c = map(int, input().split())
    s -= 1
    c -= 1
    record[c][s] += 1
    record[c][t] -= 1
cum = []
for i in range(C):
    tmp = [record[i][0]]
    for j in range(10 ** 5 - 1):
        tmp.append(tmp[-1] + record[i][j + 1])
    cum.append(tmp)
ans = 0
for i in range(10 ** 5):
    tmp = 0
    for j in range(C):
        tmp += cum[j][i]
    ans = max(tmp, ans)
print(ans)

Submission status: Runtime Error

Solution code:
n,C = map(int, input().split())
stc=[list(map(int,input().split())) for _ in range(n)]
time = [0]*(10**5+1)
for s,t,c in stc:
    time[s-1]+=1
    time[t]-=1
ans = time[0]
for i in range(10**5+1):
    time[i+1] += time[i]
    if time[i+1] > ans:
        ans = time[i+1]
print(ans)

Submission status: Runtime Error

Solution code:
n,C = map(int, input().split())
stc=[list(map(int,input().split())) for _ in range(n)]
time = [0]*(10**5+1)
for s,t,c in stc:
    time[s]+=1
    time[t+1]-=1
ans = time[0]
for i in range(10**5):
    time[i+1] += time[i]
    if time[i+1] > ans:
        ans = time[i+1]
print(ans)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
def main():
    n, c = map(int, input().split())
    # cs[0]とcs[-1]はindex error除け。
    cs = [0] * 10002

    for _ in range(n):
        s, t, c = map(int, input().split())
        cs[s - 1] += 1
        cs[t + 1] -= 1
    cur = 0
    r = 0
    for cse in cs:
        cur += cse
        r = max(r, cur)
    print(r)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
def main():
    n, c = map(int, input().split())
    # cs[0]とcs[-1]はindex error除け。
    cs = [0] * 10001

    for _ in range(n):
        s, t, c = map(int, input().split())
        cs[s] += 1
        cs[t + 1] -= 1
    cur = 0
    r = 0
    for cse in cs:
        cur += cse
        r = max(r, cur)
    print(r)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
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 
#mod = 998244353
from decimal import *
import numpy as np
#decimal.getcontext().prec = 10

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]

#print(m)
cnt = [0]*(15)

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


cnt = list(accumulate(cnt))
#print(cnt)
print(max(cnt))