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:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,C=map(int,input().split())
    l=[]
    for i in range(N):
        l.append(list(map(int,input().split())))
    l.sort(key=lambda t:(t[2],t[1]))
    a=[0]*(10**5+1)
    ss,tt,cc=-1,-1,-1
    for s,t,c in l:
        if s==tt and c==cc:
            a[tt]+=1
            a[t]-=1
        else:
            a[s-1]+=1
            a[t]-=1
        ss,tt,cc=s,t,c
    ans=0
    tmp=0
    for x in a:
        tmp+=x
        ans=max(ans,tmp)
    print(ans)
            

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate

n,c = map(int, input().split())
stc = sorted([list(map(int, input().split())) for i in range(n)])
finish = [1] * (c+1)
record = [0] * (10 ** 5 + 2) 
ans = 1
for s,t,c in stc:
  if finish[c] != s:
    s -= 1
  finish[c] = t
  record[s] += 1
  record[t] -= 1
ans = max(list(accumulate(record)))
assert ans >= 1
assert ans <= n
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

MAX_T = 10 ** 5 + 100
MAX_C = 30

n, c = map(int, input().split())
time = {c: [] for c in range(1, MAX_C + 1)}

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

n_program = [0 for _ in range(MAX_T + 1)]

for c in range(1, MAX_C + 1):

    recording = [0 for _ in range(MAX_T + 1)]

    for s, t in time[c]:
        recording[s] += 1
        recording[t + 1] -= 1

    recording = accumulate(recording)

    for i, r in enumerate(recording):
        if r:
            n_program[i] += 1

answer = max(n_program)
print(answer)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,c = map(int,readline().split())
ch = [[[0,0]] for _ in range(c)]
for i in range(n):
    s,t,c = map(int,readline().split())
    ch[c-1].append([s,t])
imos = [0]*(10**5+1)
for i in ch:
    i.sort()
    for j in range(1,len(i)):
        s,t = i[j]
        if i[j-1][1] < s:
            imos[s-1] += 1
        else:
            imos[s] += 1
        imos[t] -= 1

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

print(max(imos))

Submission status: Accepted

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

S=[[] for _ in range(10**5+1)]
T=[[] for _ in range(10**5+1)]

for s,t,c in STC:
    S[s].append(c)
    T[t].append(c)

used=set()
ans=0
for i in range(10**5+1):
    start=set()
    finish=set()
    for s in S[i]:
        start.add(s)
    for t in T[i]:
        finish.add(t)
    ans=max(ans,len(used)+len(start-finish))
    used=used-finish|start
print(ans)

Submission status: Accepted

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

import heapq  # heapqライブラリのimport
tv=[-1]
heapq.heapify(tv)  # リストを優先度付きキューへ
#print(heapq.heappop(a))  # 最小値の取り出し
#heapq.heappush(a, -2)
ch=[0]*c

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

stc.sort()

for item in stc:
    s,t,c=item[0],item[1],item[2]
    temp=heapq.heappop(tv)
    if temp<s:
        heapq.heappush(tv,t)
    elif temp==s and ch[c-1]==temp:
        heapq.heappush(tv, t)
    else:
        heapq.heappush(tv,temp)
        heapq.heappush(tv,t)
    ch[c-1]=t
    #print(tv)
print(len(tv))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N, C = [int(x) for x in input().split()]
    STC = [[int(x) for x in input().split()] for _ in range(N)]

    S = [[] for _ in range(10 ** 5 + 1)]
    T = [[] for _ in range(10 ** 5 + 1)]

    for s, t, c in STC:
        S[s].append(c)
        T[t].append(c)

    used = set()
    ans = 0
    for i in range(10 ** 5 + 1):
        sused = set()
        tused = set()

        for s in S[i]:
            sused.add(s)
        for t in T[i]:
            tused.add(t)

        ans = max(ans, len(used) + len(sused - tused))
        used = used - tused | sused

    print(ans)








if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

al= []
for i in range(c):
    if len(l[i]) > 1:
        l[i].sort()
        now2 = l[i][0][1]
        now1 = l[i][0][0]
        check = False
        for j in range(1,len(l[i])):
            if l[i][j][0] == now2:
                now2 = l[i][j][1]
            else:
                al.append([[now1,now2],i])
                check = True
                now1 = l[i][j][0]
                now2 = l[i][j][1]
        if not check:
            al.append([[now1,now2],i])

    else: 
        if l[i]:
            al.append([l[i][0],i])
al.sort()

count = [[-1,-1]]
for i in range(len(al)):
    a,b,c = al[i][0][0], al[i][0][1],al[i][1]
    check = False
    for j in range(len(count)):
        if count[j][0] < a:
            count[j] = [b,c]
            check = True
            break
    if not check:
        count.append([b,c])

print(len(count))

Submission status: Accepted

Solution code:
from collections import defaultdict
import numpy as np
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, C = map(int, input().split())
    MAX = 10 ** 5 + 2
    vals = [0] * MAX
    D = defaultdict(list)
    for _ in range(N):
        s, t, c = map(int, input().split())
        D[c].append((s, t))

    for k, v in D.items():
        prev = -1
        v.sort(key=lambda x: x[0])
        for s, t in v:
            if prev == s:
                vals[prev + 1] += 1
                vals[t + 1] -= 1
            else:
                vals[s] += 1
                vals[t + 1] -= 1
            prev = t

    cumsum = np.cumsum(vals)
    ans = max(cumsum)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N,C = LI()
p = [[(0,0)] for _ in range(C+1)]
for _ in range(N):
    s,t,c = LI()
    p[c].append((s,t))

im = [0 for _ in range(10**5+1)]
for x in p:
    x.sort()
    for i in range(1,len(x)):
        s,t = x[i]
        if x[i-1][1] < s: s -= 1
        im[s] += 1
        im[t] -= 1

ans = 0
tm = 0
for t in im:
    tm += t
    ans = max(ans,tm)
print(ans)

Submission status: Accepted

Solution code:
N,C=map(int, input().split())
A=[list(map(int, input().split())) for _ in range(N)]
D=[[] for i in range(C)]
DD=[[] for i in range(C)]
for s,t,c in A:
  D[c-1].append([s,t])
for i in range(C):
  E=sorted(D[i])
  e=len(E)
  for j in range(e):
    if j==0:
      DD[i].append([E[j][0],E[j][1]])
    elif j!=0 and E[j][0]==E[j-1][1]:
      DD[i][-1][-1]=E[j][1]
    else:
      DD[i].append([E[j][0],E[j][1]])
ANS=[0]*(10**5+3)
for i in range(C):
  F=DD[i]
  for i,j in F:
    ANS[i]+=1
    ANS[j+1]-=1
ans=0
d=0
for i in ANS:
  d+=i
  ans=max(d,ans)
print(ans)

Submission status: Accepted

Solution code:
# ある時点の重複番組数を前からカウントして、最大値が答え
# s順に並べて、ループごとに重複数を増やしつつ、
# 終了キューにtを追加
# 番組追加するごとに終了キューの中身をチェック
# 同じチャンネルだったら、終了キューt <= 現在時刻 のときに終了キューから外せる
# 違うチャンネルだったら、終了キューt < 現在時刻となる
# チャンネルごとにheapqを持つ

N,C = map(int,input().split())
import heapq
endq = [[] for i in range(C)]
for i in range(C):
  heapq.heapify(endq[i])
progs = [None] * N
for i in range(N):
  s,t,c = map(int,input().split())
  progs[i] = [s,t,c-1]

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

ans = 0
cur = 0

for i in range(N):
  s,t,c = progs[i]
  # 時刻sに終了する番組をチェックする
  # まず同チャンネルのものが時刻sに終了していたら、それを外すことが出来る
  while endq[c]:
    endt = heapq.heappop(endq[c])
    if endt <= s:
      cur -= 1
    else:
      heapq.heappush(endq[c],endt)
      break
  
  # 他のチャンネルをチェックする
  for endc in range(C):
    if endc == c:
      continue # 同じチャンネルはチェック済み
    while endq[endc]:
      endt = heapq.heappop(endq[endc]) # 各チャンネルのキューから取り出す
      if endt < s:
        cur -= 1
      else:
        heapq.heappush(endq[endc],endt)
        break
  # 今回の番組を格納する
  cur += 1
  heapq.heappush(endq[c],t)
  if cur > ans:
    ans = cur

print(ans)

Submission status: Accepted

Solution code:
n,C = map(int,input().split())
imos = [0]*(10**5+2)
ch = [set() for _ in range(C)]
for i in range(n):
    s,t,c = map(int,input().split())
    c -= 1
    if s in ch[c]:
        ch[c].remove(s)
        imos[s+1] +=1
    else:
        ch[c].add(s)
        imos[s] += 1
    if t in ch[c]:
        ch[c].remove(t)
        imos[t] -= 1
    else:
        ch[c].add(t)
        imos[t+1] -= 1
ans = 0
cnt = 0
for i in imos:
    cnt += i
    ans = max(ans,cnt)
print(ans)

Submission status: Accepted

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

LEN = 10 ** 5 + 7
d = [[0] * LEN for _ in range(C + 1)]
for s, t, c in X:
    d[c][s] += 1
    d[c][t + 1] -= 1

for i in range(C + 1):
    for j in range(LEN - 1):
        d[i][j + 1] += d[i][j]

x = [0] * LEN
for i in range(C + 1):
    for j in range(LEN):
        x[j] += int(d[i][j] > 0)
        
print(max(x))

Submission status: Accepted

Solution code:
n,C = map(int,input().split())
imos = [0]*(10**5+2)
ch = [set() for _ in range(C)]
for i in range(n):
    s,t,c = map(int,input().split())
    c -= 1
    if s in ch[c]:
        ch[c].remove(s)
        imos[s+1] +=1
    else:
        ch[c].add(s)
        imos[s] += 1
    if t in ch[c]:
        ch[c].remove(t)
        imos[t] -= 1
    else:
        ch[c].add(t)
        imos[t+1] -= 1
ans = 0
cnt = 0
for i in imos:
    cnt += i
    ans = max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
N, C = tuple(map(int, input().split()))
events = []
tmax = 0
dic=dd(list)
for i in range(N):
    s, t, c = map(int, input().split())
    dic[c].append((s,t))
eps = 0.5
for k,v in dic.items():
    v1 = sorted(v)
    lev = len(v1)
    prev = [-1,-1]
    for i,val in enumerate(v1):
        if tmax < val[1]:
            tmax = val[1]
        if prev == [-1,-1]:
            prev[0] = val[0]
            prev[1] = val[1] # end_time
            if lev != 1:
                continue
            else:
                events.append((prev[0]-eps, 1))
                events.append((prev[1], 0))
                break
        if prev[1] == val[0]:# prev_end == now_start
            prev[1] = val[1]
            if i == lev - 1:
                events.append((prev[0] - eps, 1))
                events.append((prev[1], 0))
                break
        else:
            events.append((prev[0]-eps, 1))
            events.append((prev[1], 0))
            prev[0] = val[0]
            prev[1] = val[1]
            if i==lev-1:
                events.append((val[0]-eps, 1))
                events.append((val[1], 0))
                break
events.sort()
idx = 0
cnt = 0
res = 0
events.append((0,-1))
for t in range(tmax + 1):
    while events[idx][0] <= t:
        event = events[idx]
        if event[1] == 1:
            cnt += 1
            if res < cnt:
                res = cnt
        elif event[1] == 0:
            cnt -= 1
        else:
            break
        idx += 1
print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict
N,C=map(int,input().split())

event_list=[]
for i in range(N):
  s,t,c=map(int,input().split())
  event_list.append((s-0.5,c))
  event_list.append((t,-c))
event_list.sort()
#print(event_list)

answer=0
cdic=defaultdict(int)
for t,c in event_list:
  if c>0:
    cdic[c]+=1
    answer=max(answer,len(cdic))
  else:
    cdic[-c]-=1
    if cdic[-c]==0:
      cdic.pop(-c)
  #print(cdic)

print(answer)

Submission status: Accepted

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

N, C = [int(x) for x in input().split()]
imos = [0]*(10**6 + 2)
stc = [[] for _ in range(31)]
for _ in range(N):
    tmp = [int(x) for x in input().split()]
    stc[tmp[2]].append([tmp[0], tmp[1]])

for i in range(C + 1):
    if len(stc[i]) == 0:
        continue
    stc[i].sort()
    s, t = stc[i][0][0], stc[i][0][1]
    new_stc_i = []
    flag = 1
    for j in range(1, len(stc[i])):
        flag = 0
        if t == stc[i][j][0]:
            t = stc[i][j][1]
            flag = 1
        else:
            new_stc_i.append([s, t])
            s = stc[i][j][0]
            t = stc[i][j][1]
    if flag:
        new_stc_i.append([s, t])
    stc[i] = new_stc_i

for i in range(C + 1):
    stc_i = stc[i]
    for j in stc_i:
        s, t = j 
        s *= 10
        t *= 10
        imos[max(0, s - 5)] += 1
        imos[t] -= 1

from itertools import accumulate

csum = list(accumulate(imos))

print(max(csum))

Submission status: Accepted

Solution code:
def main():
    N,C = [int(_n) for _n in input().split()]
    L = 100010
    table = [[0]*L for _ in range(C)]
    for i in range(N):
        s,t,c = [int(_n) for _n in input().split()]
        c -= 1
        s -= 1
        t -= 1
        table[c][s] += 1
        table[c][t+1] -= 1 
    for c in range(C):
        for j in range(L-1):
            table[c][j+1] += table[c][j]
    for i in range(C):
        for j in range(L):
            table[i][j] = min(1, table[i][j])
    for j in range(L):
        for c in range(C-1):
            table[c+1][j] += table[c][j]
    print(max(table[C-1]))
    # print(table)
    # print(table)
    # acc = [0] * len(times)
    # progs.sort(key = lambda x:x[2])



main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from heapq import heappush
    N, C = map(int, input().split())
    table = [[0]*10**5 for _ in range(C)]
    for _ in range(N):
        s, t, c = map(int, input().split())
        s -= 1
        t -= 1
        c -= 1
        for i in range(s, t + 1):
            table[c][i] = 1
            
    ans = 0
    for i in range(10**5):
        tmp = sum(table[j][i] for j in range(C))
        ans = max(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,c,*stc = map(int,open(0).read().split())
stc = list(zip(stc[::3],stc[1::3],stc[2::3]))

stc.sort()

record = []

for s,t,c in stc:
    
    for i,(rt,rc) in enumerate(record):
        if s-0.5 >= rt:
            record[i] = (t,c)
            break
        elif c == rc and  s>= rt:
            record[i] = (t,c)
            break
    else:
        record.append((t,c))
    
    record.sort(reverse=True)

print(len(record))

Submission status: Accepted

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


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

TABLE = [[0] * 10**5 for _ in range(c)]
for _ in range(n):
    s, t, i = [int(x) - 1 for x in input().split()]
    for j in range(s, t + 1):
        TABLE[i][j] = 1

answer = 0
for j in range(10**5):
    temporary = sum(TABLE[i][j] for i in range(c))
    answer = max(answer, temporary)

print(answer)

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
t=[[0 for i in range(100001)] for j in range(c)]

for i in range(n):
    si,ti,ci = map(int,input().split())
    for j in range(si,ti+1):
        t[ci-1][j] = 1
print(max(sum(t[j][i] for j in range(c)) for i in range(100001)))

Submission status: Accepted

Solution code:
# solution

import io
import sys
import math
from itertools import accumulate as acc

data=sys.stdin.readline

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


array=[[0 for i in range(10**5+1)] for i in range(C+1)]

rec=[0 for i in range(10**5+1)]

for i in range(N):
    s,t,c=map(int,data().split())
    recs,rect=array[c][s],array[c][t]
    if recs==0 and rect==0:
        rec[s-1]+=1
        rec[t]-=1
    elif recs==0 and rect==1:
        rec[s-1]+=1
        rec[t-1]-=1
    elif recs==1 and rect==0:
        rec[s]+=1
        rec[t]-=1
    elif recs==1 and rect==1:
        rec[s]+=1
        rec[t-1]-=1

    array[c][s],array[c][t]=1,1

tmp=0
ans=0
for i in range(10**5):
    tmp+=rec[i]
    ans=max(tmp,ans)
print(ans)

Submission status: Accepted

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

time = [0 for _ in range(2*10**5 + 2)]

for i in range(C):
    w = [0 for _ in range(2*10**5 + 2)]
    for s,t,c in pro:
        if c == i + 1:
            w[2*s-1] += 1
            w[2*t] -= 1
    for j in range(2*10**5+1):
        w[j+1] += w[j]
        if w[j+1]:
            time[j+1] += 1

print(max(time))

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import accumulate


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

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

for name, times in timetables.items():
    times.sort()
    new = []
    for i, time in enumerate(times):
        s, t = time
        if i == 0:
            new.append([s, t])
            continue
        if s == new[-1][1]:
            new[-1][1] = t
        else:
            new.append([s, t])
    timetables[name] = new

time_count = [0] * 100010
for name, times in timetables.items():
    for s, t in times:
        time_count[s] += 1
        time_count[t + 1] -= 1

acc = accumulate(time_count)

print(max(acc))

Submission status: Accepted

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

ans = 0

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

time = 10**5+1

c_imos = [[0 for i in range(time)] for j in range(c)]

for i in range(n):
    for j in range(stc[i][1]-stc[i][0]+1):
        c_imos[stc[i][2]-1][stc[i][0]-1+j] = 1


"""
for i in range(n):
    c_imos[stc[i][2]-1][stc[i][0]-1] += 1
    c_imos[stc[i][2]-1][stc[i][1]] -= 1
"""
#nd_v = [[0 for i in range(time)] for j in range(c)]
"""
for i in range(c):
    for j in range(time):
        if j == 0:
            if c_imos[i][j] == 1:
                nd_v[i][j] = 1
        else:
            nd_v[i][j] = nd_v[i][j-1] + c_imos[i][j]
"""
"""
for i in range(c):
    for j in range(time):
        if nd_v[i][j] >= 2:
            nd_v[i][j] = 1
"""
ans = 1

#print(c_imos)

for i in range(time):
    tmp = 0
    for j in range(c):
        tmp += c_imos[j][i]
    #print(i,tmp)
    ans = max(tmp,ans)

print(ans)

exit()
    
c_num = stc[0][2]
t_num = stc[0][1]
idx = 0
print(stc)
for i in range(1,n):
    print(t_num,i)
    if stc[idx+i][2] == c_num:
        if stc[idx+i][0] == t_num:
            stc[idx+i-1][1] = stc[idx+i][1]
            t_num = stc[idx+i][1]
            del stc[idx+i]
            idx -= 1
        else:
            print(t_num,t_num,t_num)
            c_num = stc[idx+i][2]
            t_num = stc[idx+i][1]

stc.sort(key=lambda x:x[1])
print(stc)
exit()
tmp = stc[0][1]

ans = 1
ans_tmp = 1

for i in range(1,len(stc)):
    for j in range(i+1,len(stc)):
        if tmp >= stc[j][0]:
            ans_tmp += 1
        else:
            tmp = stc[j][0]
            ans = max(ans_tmp,ans)

Submission status: Accepted

Solution code:


def submit():
    n, c = map(int, input().split())
    table_max = 10 ** 5
    table = [0 for _ in range(table_max + 1)]

    programs = []
    for _ in range(n):
        s, t, c = map(int, input().split())
        programs.append((s, t, c))
    programs.sort(key=lambda x: (x[2], x[0]))

    program_merge = [programs[0]]
    last = programs[0]
    for p in programs[1:]:
        if last[2] == p[2] and last[1] == p[0]:
            program_merge.pop()
            program_merge.append((last[0], p[1], p[2]))
        else:
            program_merge.append(p)
        last = program_merge[-1]
            

    for s, t, _ in program_merge:
        table[s - 1] += 1
        table[t] -= 1

    curr_max = 0
    for i in range(1, table_max + 1):
        table[i] += table[i - 1]
        if table[i] > curr_max:
            curr_max = table[i]

    print(curr_max)


submit()

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
# from math import gcd
import bisect
import copy
from itertools import permutations,accumulate,combinations,product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,c=map(int,input().split())
stc=[list(map(int,input().split())) for i in range(n)]
stc.sort()
lst=[0]*c
for i in range(n):
    s,t,ctmp=stc[i]
    for j in range(c):
        if lst[j]==0:
            lst[j]=stc[i]
            break
        else:
            if lst[j][2]==ctmp:
                lst[j]=stc[i]
                break
            elif lst[j][1]<s:
                lst[j]=stc[i]
                break
# print(lst)
ans=0
for i in range(c):
    if lst[i]!=0:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import heapq

def main():
    N, C = map(int, input().split())
    STC = [tuple(map(int, input().split())) for _ in range(N)]
    STC.sort()
    CC = [(0, 0)] * C
    T = []
    for s, t, c in STC:
        ps, pt = CC[c - 1]
        if ps == 0:
            CC[c - 1] = (s, t)
        elif s == pt:
            CC[c - 1] = (ps, t)
        else:
            T.append((ps, pt, c))
            CC[c - 1] = (s, t)
    for c, (s, t) in enumerate(CC):
        if s != 0:
            T.append((s, t, c + 1))
    T.sort()
    STC = T

    h = []
    e = []
    r = 0
    for s, t, c in STC:
        while h and h[0][0] <= s:
            e.append(heapq.heappop(h)[1])
        if not e:
            e.append(r)
            r += 1
        heapq.heappush(h, (t + 1, e.pop()))
    return r

print(main())

Submission status: Accepted

Solution code:
def main():
    N, C = map(int, input().split())
    l = []
    for _ in range(N):
        s, t, c = map(int, input().split())
        l.append((s,t,c))
    l.sort(key=lambda x: x[0])
    r = []
    for i in l:
        if not r:
            r.append((i[1], i[2]))
            continue
        for j, v in enumerate(r):
            if v[0] < i[0] or (v[1] == i[2] and v[0] == i[0]):
                r[j] = (i[1], i[2])
                break
        else:
            r.append((i[1], i[2]))
        r.sort(key=lambda x:x[0])
    print(len(r))
main()

Submission status: Accepted

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

Submission status: Accepted

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

n, C = map(int, input().split())
stc = []
max_t = 0
for i in range(n):
    s, t, c = map(int, input().split())
    max_t = max(max_t, t)
    stc.append([s, t, c])

len_imos = max_t+1
imos = [[0 for _ in range(len_imos)] for _ in range(C)]
for i in range(n):
    s, t, c = stc[i]
    imos[c-1][s-1] += 1
    imos[c-1][t] -= 1

for j in range(C):
    v = 0
    for i in range(len_imos):
        v += imos[j][i]
        imos[j][i] = v

ans = 0
v = 0
for i in range(len_imos):
    v = 0
    for c in range(C):
        v += 1 if imos[c][i] > 0 else 0
    ans = max(ans, v)
# print(imos)
print(ans)

Submission status: Accepted

Solution code:
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())
    T[c-1][s] += 1
    T[c-1][t] -= 1
for i in range(C):
    for j in range(10**5):
        T[i][j+1] += T[i][j]

ans = 0
for i in range(1,10**5+1):
    a = 0
    for j in range(C):
        if T[j][i] or T[j][i-1]:
            a += 1
    ans = max(ans,a)
print(ans)

Submission status: Accepted

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

t = [[0 for i in range(100001)] for j in range(c)]

for i in range(n):
    si,ti,ci = map(int,input().split())
    for j in range(si,ti+1):
        t[ci-1][j] = 1
print(max(sum(t[j][i] for j in range(c)) for i in range(100001)))

Submission status: Accepted

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

t = [[0 for i in range(100001)] for j in range(c)]

for i in range(n):
    si,ti,ci = map(int,input().split())
    for j in range(si,ti+1):
        t[ci-1][j] = 1
ans = 0
for i in range(100001):
    ans = max(ans,sum(t[j][i] for j in range(c)))
print(ans)

Submission status: Accepted

Solution code:
N,C = map(int,input().split())
imos = [[0]*100005 for i in range(30)]
for i in range(N):
    s,t,c = map(int,input().split())
    s -= 1
    c -= 1
    imos[c][s] += 1
    imos[c][t] -= 1
for c in range(C):
    for i in range(1,100005):
        imos[c][i] += imos[c][i-1]
for c in range(C):
    for i in range(1, 100005):
        if imos[c][i]:
            imos[c][i] = 1

ans = 0
for i in range(100005):
    cnt = 0
    for c in range(C):
        cnt += imos[c][i]
    ans = max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,c = map(int, input().split())
    stc = [list(map(int, input().split())) for _ in range(n)]
    rokuga = [[0]*c for _ in range(2*10**5+10)]

    for s,t,ch in stc:
        for i in range(int((s-0.5)*2), 2*t):
            rokuga[i][ch-1] = 1
    
    res = 0
    for i in range(1, 2*10**5+10):
        res = max(res, sum(rokuga[i]))
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

N, C = map(int, input().split())
MAX = 10 ** 5 + 1
table = [[0] * MAX for _ in range(C)]

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

for c in range(C):
    for x in range(MAX - 1):
        if table[c][x + 1] == 1:
            table[c][x + 1] = 0
            table[c][x] += 1

table_sum = [sum(table[c][i] for c in range(C)) for i in range(MAX)]
print(max(itertools.accumulate(table_sum)))

Submission status: Accepted

Solution code:
# N個のimosなので二次元でやる 0.5がうざいので*2する( (2*10^5) * C )

# なぜか2WAが取れない

# これ嘘解法ぽい気がする

N, C = map(int, input().split())
x = 2 * (10**5)
# x = 30  # test
imos = [[0 for _ in range(x)] for _ in range(C)]
for _ in range(N):
    s, t, c = map(int, input().split())
    s, t, c = s * 2 - 1, t * 2 - 1, c - 1
    imos[c][s - 1] += 1
    imos[c][t] -= 1
    # imos[c][s - 1] = min(1, imos[c][s - 1])  # test

for i in range(C):
    for j in range(1, x):
        imos[i][j] += imos[i][j - 1]
        # imos[i][j] = min(1, imos[i][j])  # test

ans = 0
for j in range(x):
    tmp = 0
    for i in range(C):
        tmp += min(1, imos[i][j])
    ans = max(ans, tmp)
# print("-----------")
# for x in imos:
#     print(x)
print(ans)

# 1 3
# 3 4 2

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.buffer.readline
n,c=map(int,input().split())
a=[ [0 for _ in range(10**5+2)] for _ in range(c)]
for _ in range(n):
    s,t,cc=map(int,input().split())
    cc-=1
#    print(s-1,end=' s-1\n')
    #a[cc][s-1]+=1
    #a[cc][t]-=1
    for i in range(s-1,t):
        a[cc][i]=1
'''for i in range(c):
    for j in range(1,10**5+1):
        a[i][j]+=a[i][j-1]
'''
ans=1
for j in range(0,10**5):
    su=0
#    print(c,'hello')
    for i in range(c):
#        print('asdf hello')
#        print(j,i,a[i][j])
        su+=a[i][j]
    ans=max(ans,su)
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.buffer.readline
n,c=map(int,input().split())
a=[ [0 for _ in range(10**5+2)] for _ in range(c)]
for _ in range(n):
    s,t,cc=map(int,input().split())
    cc-=1
#    print(s-1,end=' s-1\n')
    #a[cc][s-1]+=1
    #a[cc][t]-=1
    for i in range(s-1,t):
        a[cc][i]=1
'''for i in range(c):
    for j in range(1,10**5+1):
        a[i][j]+=a[i][j-1]
'''
ans=1
for j in range(0,10**5+1):
    su=0
#    print(c,'hello')
    for i in range(c):
#        print('asdf hello')
#        print(j,i,a[i][j])
        su+=a[i][j]
    ans=max(ans,su)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n, C = map(int,input().split())
cha = [[0] for _ in range(C+1)]
stc = [list(map(int, input().split())) for _ in range(n)]
stc.sort()
result = np.zeros(2*10**5)
for s, t, c in stc:
    if cha[c] == s:
        result[2*s+1:2*t] += 1
    else:
        result[2*s-1:2*t] += 1
    cha[c] = t
print(int(max(result)))

Submission status: Accepted

Solution code:
import numpy as np
n, C = map(int,input().split())
cha = [[[0,0]] for _ in range(C+1)]
stc = [list(map(int, input().split())) for _ in range(n)]
stc.sort()
for s, t, c in stc:
    if cha[c][-1][1]==s:
        cha[c][-1][1] = t
    else:
        cha[c].append([s, t])
result = np.zeros(2*10**5)
for i in range(1, C+1):
    for s, t in cha[i]:
        result[s*2-1:t*2] += 1
print(int(max(result)))

Submission status: Accepted

Solution code:
n,C=map(int,input().split())
import collections
d=collections.defaultdict(list)
for i in range(n):
    s,t,c=map(int,input().split())
    d[c].append((s,t))
T=[0 for i in range(2*10**5+3)]
for i in d.values():
    i.sort()
    T[i[0][0]*2-1]+=1
    T[i[-1][1]*2+1]-=1
    for x,y in zip(i,i[1:]):
        s1,t1=x
        s2,t2=y
        if t1!=s2:
            T[s2*2-1]+=1
            T[t1*2+1]-=1
from itertools import accumulate
T=list(accumulate(T))
print(max(T))