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:
from itertools import accumulate
N, C = map(int, input().split())
X = [[0] * (10 ** 5 + 1) for i in range(C)]
for i in range(N):
    s, t, c = map(int, input().split())
    c -= 1
    X[c][s - 1] += 1
    X[c][t] -= 1

for c in range(C):
    X[c] = list(accumulate(list(X[c])))


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

print(ans)

Submission status: Accepted

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

P = [[] for i in range(C)]

for i in range(N):
    s,t,c = list(map(int,input().split()))
    P[c-1].append([s,"S"])
    P[c-1].append([t,"T"])

P = [sorted(sorted(P[i],key=lambda x:x[1]),key=lambda x: x[0]) for i in range(C)]
#print(P)
P2 = []

for i in range(C):
    for j in range(len(P[i])):
        if P[i][j][1]=="T":
            if j!=0:
                if P[i][j][0]!=P[i][j-1][0]:
                    P2.append(P[i][j])
            else:
                P2.append(P[i][j])
        else:
            if j!=len(P[i])-1:
                if P[i][j][0]!=P[i][j+1][0]:
                    P2.append([P[i][j][0]-0.5,P[i][j][1]])
            else:
                P2.append([P[i][j][0]-0.5,P[i][j][1]])

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

count=0
max_count=0
s_buf = 0
t_buf = 0

prev = -1
for i in range(len(P)):
    if prev!=P[i][0]:
        prev=P[i][0]
        count+=s_buf-t_buf
        s_buf=0
        t_buf=0
        max_count=max(count,max_count)
    if P[i][1]=="S":
        s_buf+=1
    else:
        t_buf+=1
#print(P)
count+=s_buf-t_buf
max_count=max(count,max_count)

print(max_count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
INF = float("inf")


def solve(N: int, C: int, s: "List[int]", t: "List[int]", c: "List[int]"):
    seq = [0]*(3*10**5)
    # チャンネルを切り替えない場合、0.5秒のラグが発生しない。
    # 同じチャンネルでしりとあたまがいっしょなら、ひとつの番組にしておく
    c, s, t = zip(*sorted(sorted(zip(c, s, t), key=lambda x: x[1])))
    # いもす法
    # seq = [0]*(40)
    pre_s, pre_t, pre_c = -1, -1, -1
    for sv, tv, cv in zip(s, t, c):
        if pre_c == cv and pre_t == sv:
            seq[2*pre_t] += 1
            seq[2*tv] -= 1
        else:
            seq[2*sv-1] += 1
            seq[2*tv] -= 1
        pre_s, pre_t, pre_c = sv, tv, cv
    acc = list(accumulate(seq))
    # print(seq)
    # print(acc)
    print(max(acc))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    s = [int()] * (N)  # type: "List[int]"
    t = [int()] * (N)  # type: "List[int]"
    c = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        s[i] = int(next(tokens))
        t[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, C, s, t, c)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#coding:utf-8
from collections import defaultdict
N,C=map(int,raw_input().split())
S=[];T=[];C=[]
for i in range(N):
    s,t,c=map(int,raw_input().split())
    S.append(s);T.append(t);C.append(c)
beg=defaultdict(int)
end=defaultdict(int)
F=defaultdict(list)
for s,t,c in zip(S,T,C):
    F[c].append((s,t))
for k,v in F.iteritems():
    v.sort()
    buf=[]
    s,t=v[0]
    buf.append([s,t])
    for ss,tt in v[1:]:
        if t!=ss:
            buf.append([ss,tt])
        else:
            buf[-1][1]=tt
        s,t=ss,tt
    for s,t in buf:
        beg[2*s-1]+=1
        end[2*t]+=1
ans=-1; cur=0
for i in range(0,max(end)+100):
    cur+=beg[i]
    cur-=end[i]
    ans=max(ans,cur)
print(ans)

Submission status: Accepted

Solution code:
# 同じチャンネルだけ継続できる
# 同じチャンネルが継続しない場合、1秒余分にロス

import sys
input = sys.stdin.readline

N,C = map(int,input().split())
T = [[] for _ in range(C+1)] # cごとに(s,t)
for _ in range(N):
  s,t,c = map(int,input().split())
  T[c].append((s,t))

  
def simplify(times):
  result = []
  times.sort()
  for s,t in times:
    if result and result[-1][1] == s:
      result[-1] = (result[-1][0],t)
    else:
      result.append((s,t))
  return result

T = [simplify(x) for x in T]

# [s-0.5,t)で一つ使う
# [s-0.25,t+0.25]としてよい
# [s,t]としてよい

import numpy as np
A = np.zeros(10**5+10,dtype=np.int32)
for times in T:
  for s,t in times:
    A[s] += 1
    A[t+1] -= 1

    
answer = A.cumsum().max()
print(answer)

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
d=[[] for i in range(c)]
w=[0]*100002
for i in range(n):
    s,t,x=map(int,input().split())
    d[x-1].append((s,t))
for i in range(c):
    d[i].sort()
    e=0
    for j in range(len(d[i])):
        if len(d[i])==1:
            w[d[i][0][0]]+=1
            w[d[i][0][1]+1]-=1
        elif j==0:
            w[d[i][0][0]]+=1
            e=d[i][0][1]
        elif j+1==len(d[i]):
            if e!=d[i][j][0]:
                w[e+1]-=1
                w[d[i][j][0]]+=1
            w[d[i][j][1]+1]-=1
        else:
            if e!=d[i][j][0]:
                w[e+1]-=1
                w[d[i][j][0]]+=1
            e=d[i][j][1]
ans=chk=0
for i in w:
    chk+=i
    ans=max(ans,chk)
print(ans)

Submission status: Accepted

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


main()

Submission status: Accepted

Solution code:
N,C = [ int(it) for it in input().split() ]
li = [ [ int(it) for it in input().split() ] for i in range(N) ]

li.sort( key = lambda x:x[0] )

vi_li = [ [-1,-1] for i in range(C) ] # end_time, channel


for s,t,c in li:
  vi_li.sort( key= lambda x:x[0] + (1000000000 if x[0]==-1 else 0) )
  for vi in vi_li:
    if ( vi[1] == c ):
      if (vi[0]<=s):
        vi[0] = t
        vi[1] = c
        break
    else:
      if (vi[0]<s):
        vi[0] = t
        vi[1] = c
        break
        
print ( len( [1 for it in vi_li if it[0]!=-1 ] ) )

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc080/submissions/1829635

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

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

N_max = 10 ** 5
imos = [0] * (N_max + 1)

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 + 1 < len(ps[c]) and t == ps[c][i + 1][0]:
            cont = True
        else:
            imos[t] -= 1
            cont = False

ans = t = 0
for imo in imos:
    t += imo  # ここでシミュレート
    ans = max(ans, t)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

N, Cn = list(map(int, input().split()))
S, T, C = zip(*[list(map(int, input().split())) for _ in range(N)])

channels = np.zeros((Cn + 1, 10 ** 5 + 1), dtype=int)
for s, t, c in zip(S, T, C):
    channels[c][s - 1] += 1
    channels[c][t] -= 1
# 同じチャンネルで連続すると 2 になっちゃうので 1 にする
counts = np.minimum(1, channels.cumsum(axis=1)).sum(axis=0)
print(counts.max())

Submission status: Accepted

Solution code:
from collections import defaultdict

d = defaultdict(lambda:defaultdict(lambda:0))

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

using = [0]*C
ma = 0

for i in sorted(d.keys()):
    e = d[i]
    #print(e)
    ekeys = e.keys()
    for j in ekeys:
        if e[j] == 1:
            using[j-1] = 1
    ma = max(ma,sum(using))
    #print(ma)
    for j in ekeys:
        if e[j] == -1:
            using[j-1] = 0

print(ma)

#   時刻tに1個以上のイベントがあるならば
#       録画を開始する
#       録画しているデッキの数を数える
#       録画を終了する

Submission status: Accepted

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

Submission status: Accepted

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

sm = [0 for _ in range(2 * (pow(10, 5) + 1))]
for _c in range(c):
  tt = [0 for _ in range(2 * (pow(10, 5) + 1))]
  for s, t, c in stc:
    if c == _c + 1:
      tt[s * 2 - 1] += 1
      tt[t * 2] -= 1
  for i in range(1, len(tt)):
    tt[i] += tt[i-1]
  for i in range(len(sm)):
    if tt[i] > 0:
      sm[i] += 1

print(max(sm))

Submission status: Accepted

Solution code:
MAX = 114514

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

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

Y=[]
for z in [sorted(z) for z in Z if len(z) > 0]:
	for i in range(len(z)-1):
		if z[i][1] == z[i+1][0]:
			z[i+1][0] = z[i][0]
		else:
			Y.append(z[i])
	Y.append(z.pop())

X=[0 for _ in range(MAX)]
for s,t in Y:
	X[s] += 1
	X[t+1] -= 1

for i in range(1, MAX):
	X[i] += X[i-1]

print(max(X))

Submission status: Accepted

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

l=[[]for i in range(C)]
for i in range(N):
    s,t,c=map(int,input().split())
    l[c-1].append([s,t])
    
for i in range(C):
    if len(l[i])>=2:
        l[i].sort()
    #print(l)
        X=[]
        Y=l[i][0]
        for j in range(1,len(l[i])):
            
            #if i==2:
                #print(l[i],j)
            if j!=len(l[i])-1:
                #if i==2:
                    #print(Y[1],l[i][j][0])
                if Y[1]==l[i][j][0]:
                    Y[1]=l[i][j][1]
                else:
                    X.append(Y)
                    Y=l[i][j]
                    #print(Y)
            else:
                if Y[1]==l[i][j][0]:
                    Y[1]=l[i][j][1]
                    X.append(Y)
                else:
                    X.append(Y)
                    X.append(l[i][j])
        l[i]=X
#print(l)
TV=[0 for i in range(2*10**5+5)]

for i in range(C):
    for j in range(len(l[i])):
        TV[l[i][j][0]*2-1]+=1
        TV[l[i][j][1]*2]-=1
#print(TV[:10])
ANS=[TV[0]]
for i in range(1,len(TV)):
    ANS.append(ANS[i-1]+TV[i])
print(max(ANS))

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math


## input
N,C = map(int, input().split())
Cn = [[0 for j in range(10**5+1)] for i in range(C)]
An = [0 for j in range(10**5+1)]
for i in range(N):
  s,t,c = map(int, input().split())
  if Cn[c-1][s] == -1:
    An[s] += 1
  else:
    An[s-1] += 1
  if Cn[c-1][t] == 1:
    An[t-1] -= 1
  else:
    An[t] -= 1    

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

for i in range(1,10**5+1):
  An[i] += An[i-1]

print(max(An))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np

def solve(N: int, C: int, s: "List[int]", t: "List[int]", c: "List[int]"):
    torec = np.zeros((C, max(t)+1), int)
    for i in range(N):
        torec[c[i]-1][s[i]:t[i]+1] = 1
    print(np.max(np.sum(torec, axis=0)))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    s = [int()] * (N)  # type: "List[int]" 
    t = [int()] * (N)  # type: "List[int]" 
    c = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        s[i] = int(next(tokens))
        t[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, C, s, t, c)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

channells = {}
for i in range(C+1):
    channells[i] = []
max_end = -1

for i in range(N):
    s,g,c = tv_times[i]
    max_end = max(max_end,g)
    channells[c] += [s,g]

tv_times = []
f = [0 for i in range(max_end+1)]
for cha in channells.keys():
    remove_list = []
    time = channells[cha]
    time.sort()
    for i in range(1,len(time)-1):
        if time[i] == time[i+1]:
            remove_list.append(time[i])
    time = list(set(time)-set(remove_list))
    time.sort()
    for i in range(len(time)//2):
        f[max(time[2*i]-1,0)] += 1
        f[time[2*i+1]] -= 1
ans = -1
for i in range(1,max_end+1):
    f[i] += f[i-1]
    if ans < f[i]:
        ans = f[i]

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N,C=map(int,input().split())

nofc=np.zeros((C,10**5),dtype=int)

for i in range(N):
  s,t,c=map(int,input().split())
  vec=np.ones(t-s+1,dtype=int)
  nofc[c-1][s-1:t]=vec
print(int(max(np.sum(nofc,axis=0))))

Submission status: Accepted

Solution code:
from collections import defaultdict
from copy import deepcopy
from math import log
from itertools import accumulate

N,C=map(int,input().split())
T=10**5+1
programs=defaultdict(list)
for i in range(N):
    s,t,c=map(int,input().split())
    programs[c].append((s,t))
imos=[0]*(T)
for c,p in programs.items():
    p.sort()
    ps,pt=p[0]
    for s,t in p[1:]:
        if pt==s:
            pt=t
            continue
        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:
N, C = map(int, input().split())
ch = [[False for i in range(100001)] for j in range(C+1)]

for i in range(N):
    s, t, c = map(int, input().split())
    for j in range(s, t+1):
        ch[c][j] = True
ans = 0
for i in range(100001):
    count = 0
    for j in range(1, C+1):
        if ch[j][i]:
            count += 1

    ans = max(count, ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


N, C = mi()
time = [0 for i in range(10 ** 5 + 10)]
use = [[] for i in range(10 ** 5 + 10)]
F = []
for i in range(N):
    F.append(lmi())
F.sort(key=lambda x: x[0])
# print(F)
for s, t, c in F:
    use[t].append(c)
    if c in use[s]:
        time[s] += 1
    else:
        time[s-1] += 1
    time[t] -= 1
# print(time[0:100])
timesum = np.cumsum(np.array(time))
# print(use[0:100])
print(max(timesum))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,a,b = LI()
    print(min(n*a,b))
    return

#B
def B():
    s = S()
    print(s.count("1"))
    return

#C
def C():
    n = list(map(int, S()))
    k = 0
    s = sum(n)
    for i in range(len(n)):
        k *= 10
        k += n[i]
    if k%s == 0:
        print("Yes")
    else:
        print("No")
    return

#D
def D():
    n = I()
    a = LI()
    ans = float("inf")
    for i in range(n):
        m = 0
        while a[i]%2 == 0:
            m += 1
            a[i] //= 2
        ans = min(m,ans)
    print(ans)
    return

#E
def E():
    n = I()
    f = LIR(n)
    p = LIR(n)

    return

#F
def F():
    n,k = LI()
    a = LI()
    d = defaultdict(int)
    for i in a:
        d[i] += 1
    d = list(d.values())
    d.sort()
    ans = 0
    for i in range(len(d)-k):
        ans += d[i]
    print(ans)
    return

#G
def G():
    n,c = LI()
    ch = LIR(n)
    T = [[0 for i in range(100002)] for j in range(c+1)]
    for s,t,cha in ch:
        T[cha-1][s] += 1
        T[cha-1][t+1] -= 1
    for i in range(c):
        for j in range(100000):
            T[i][j+1] += T[i][j]
            if T[i][j] >= 1:
                T[i][j] = 1
    ans = 0
    for i in range(100001):
        m = 0
        for j in range(c+1):
            m += T[j][i]
        ans = max(m,ans)
    print(ans)
    return

#H
def H():
    return

#I
def I_():
    return

#J
def J():
    return

#Solve
if __name__ == "__main__":
    G()

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
table=[[0]*10**5for 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 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,ch = li()
MAX_T = 10**5+1

program = [[0]*MAX_T for _ in range(ch)]

endset = [set() for _ in range(ch)]
stc = []

for _ in range(n):
    s,t,c = li()
    c -= 1
    
    stc.append((s,t,c))
    endset[c].add(t)
    
stc.sort(key=lambda x:x[0])
    
for s,t,c in stc:
    if s in endset[c]:
        program[c][s] += 1
        program[c][t] -= 1
    else:
        program[c][s-1] += 1
        program[c][t] -= 1
    
for ci in range(ch):
    program[ci] = list(accumulate(program[ci]))
    
print(max([sum(time_span) for time_span in zip(*program)]))

Submission status: Accepted

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

_l = [[0 for _ in range(2*int(1e5+1))] for _ in range(C+1)]

for s,t,c in STC:
  if _l[c][2*s] == -1:
    _l[c][2*s] = 0
    _l[c][2*t] = -1
  else:
    _l[c][2*s-1] = 1
    _l[c][2*t] -= 1

import numpy as np

_l = np.array(_l)

ac = (_l.sum(axis=0)).cumsum()
print(max(ac))

Submission status: Accepted

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

for c in range(C + 1):
    TimeTable[c] = list(accumulate(TimeTable[c]))


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

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
n, c = map(int, input().split())
tmp_info = [list(map(int, input().split())) for i in range(n)]

tmp_info = sorted(tmp_info, key=itemgetter(2,1))
info = []
for i in range(n):
    if not info:
        info.append(tmp_info[i])
    elif info[-1][1] == tmp_info[i][0] and info[-1][2] == tmp_info[i][2]:
        info[-1][1] =tmp_info[i][1]
    else:
        info.append(tmp_info[i])
info = sorted(info, key=itemgetter(1))
n = len(info)
li = []

for i in range(n):
    li = sorted(li, reverse=True)
    for j in range(len(li)):
        if info[i][0] > li[j]:
            li[j] = info[i][1]
            break
    else:
        li.append(info[i][1])
        
print(len(li))

Submission status: Accepted

Solution code:
from numpy import cumsum
n, c = [int(item) for item in input().split()]
stc = [[int(item) for item in input().split()] for _ in range(n)] 
stc.sort(key=lambda x: (x[2], x[0]))

timeline = [0] * (10**5 + 1)
prev_c = -1 
for s, t, c in stc:
    if prev_c != c:
        prev_t = -100
    if prev_t != s:
        timeline[s-1] += 1
        timeline[t] += -1
    else:
        timeline[s] += 1
        timeline[t] += -1
    prev_t = t
    prev_c = c

print(max(cumsum(timeline)))

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: Accepted

Solution code:
from heapq import heappush, heappop

# 入力
N, C = map(int, input().split())
s, t, c = zip(*(map(int, input().split()) for _ in range(N)))

# 優先度付きキューを用いてシミュレーション
Q = []
p = [0 for _ in range(C + 1)]
ans = 0
for x, y, z in sorted(zip(s, t, c)):
    while Q and (Q[0] < x or Q[0] == x == p[z]):
        p[z] = 0
        heappop(Q)
    p[z] = y
    heappush(Q, y)
    ans = max(ans, len(Q))

# 出力
print(ans)

Submission status: Accepted

Solution code:
N,C=map(int,input().split())
from collections import defaultdict
cannel={i:[] for i in range(1,1+C)}
check=[tuple(map(int,input().split())) for i in range(N)]
check.sort(key=lambda x:x[0])
for x in check:
    s,t,c=x
    if cannel[c]==[]:
        cannel[c].append((max(0,s-1),t))
    elif s-cannel[c][-1][1]<=1:
        cannel[c][-1]=(cannel[c][-1][0],t)
    else:
        cannel[c].append((max(0,s-1),t))
start=defaultdict(int)
end=defaultdict(int)
for c in range(1,1+C):
    for x in cannel[c]:
        start[x[0]]+=1
        end[x[1]]+=1
ans=0
now=0
for i in range(10**5+1):
    now+=start[i]-end[i]
    ans=max(ans,now)
print(ans)

Submission status: Accepted

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

data = []

for i in range(n):
    s,t,h = map(int,input().split())
    data.append((s,t,h))

data.sort()

record = []

for s,t,h in data:
    flag = False
    for track in record:
        if track[0]<=s and track[1]==h:
            track[0]=t
            track[1]=h
            flag = True
            break
        elif track[0]<s and track[1]!=h:
            track[0]=t
            track[1]=h
            flag = True
            break
    if not flag:
        record.append([t,h])

print(len(record))

Submission status: Accepted

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


R = [[stc[0][1],stc[0][2]]]
for s,t,c in stc[1:]:
    for i in range(len(R)):
        tr,cr = R[i][0],R[i][1]
        if c == cr and tr <=s:
            R[i] = [t,c]
            break
        if c!=cr and tr <s:
            R[i] = [t,c]
            break
    else:
        R.append([t,c])

print(len(R))

Submission status: Accepted

Solution code:
##########################
from collections import defaultdict as ddict
N, C = map(int, input().split())
imos = [0] * (10**5 + 2)
last_s_by_c = ddict(lambda: 1)
last_t_by_c = ddict(int)
stc = [list(map(int, input().split())) for i in range(N)]
for s, t, c in sorted(stc, key=lambda x: x[1]):
	if last_t_by_c[c] != s:
		imos[last_s_by_c[c] - 1] += 1
		imos[last_t_by_c[c]] -= 1
		last_s_by_c[c] = s
	last_t_by_c[c] = t
for c in last_s_by_c:
	imos[last_s_by_c[c] - 1] += 1
	imos[last_t_by_c[c]] -= 1
for i in range(10**5 + 1):
	imos[i + 1] += imos[i]
print(max(imos))

Submission status: Accepted

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

R = [[STC[0][1], STC[0][2]]]
for s, t, c in STC[1:]:
    for i in range(len(R)):
        t_r, c_r = R[i][0], R[i][1]
        if c == c_r and t_r <= s:
            R[i] = [t, c]
            break
        if c != c_r and t_r < s:
            R[i] = [t, c]
            break
    else:
        R.append([t, c])
        
print(len(R))

Submission status: Accepted

Solution code:
n,c = map(int,input().split())
sortls = [list(map(int,input().split())) for i in range(n)]
sortls.sort(key = lambda k:(k[2],k[0]))
sortls.append([sortls[-1][0],sortls[-1][1],sortls[-1][2]+1])
count = 0;ls = [];start = -1;tf = False
while True:
    if tf:
        if sortls[count][1] == sortls[count+1][0] and sortls[count][2] == sortls[count+1][2]:
            pass
        else:
            ls.append([start,sortls[count][1],sortls[count][2]])
            tf = False
    elif sortls[count][1] != sortls[count+1][0] or sortls[count][2] != sortls[count+1][2]:
        ls.append(sortls[count])
    elif sortls[count][2] == sortls[count+1][2]:
        start = sortls[count][0]
        tf = True
    else:
        ls.append(sortls[count])
    count += 1
    if count > n-1:break

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
#def input():
#    return sys.stdin.readline()[:-1]

'''
n=int(input())
for i in range(n):
    a[i]=int(input())
    a[i],b[i]=map(int,input().split())
a=[int(x) for x in input().split()]
n,m=map(int,input.split())
from operator import itemgetter
a = [(1, "c", 1), (1, "b", 3), (2, "a", 0), (1, "a", 2)]
print(sorted(a))  # 0 番目の要素でソート、先頭の要素が同じなら 1 番目以降の要素も見る
print(sorted(a, key=itemgetter(0)))  # 0 番目の要素だけでソート
print(sorted(a, key=itemgetter(0, 2)))  # 0 番目と 2 番目の要素でソート
print(sorted(a, key=lambda x: x[0] * x[2]))  # 0 番目の要素 * 2 番目の要素でソート
print(sorted(a, reverse=True))  # 降順にソート
a.sort()  # 破壊的にソート、sorted() よりも高速
try: # エラーキャッチ list index out of range
    for i in range():
        k=b[i]
except IndexError as e:
    print(i)
'''

test_data1 = '''\
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
'''

test_data2 = '''\
2
1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 1 1
0 -2 -2 -2 -2 -2 -1 -1 -1 -1 -1
0 -2 -2 -2 -2 -2 -1 -1 -1 -1 -1
'''

test_data3 = '''\

'''
td_num=1

def GetTestData(index):
    if index==1:
        return test_data1
    if index==2:
        return test_data2
    if index==3:
        return test_data3

if False:
    with open("../test.txt", mode='w') as f:
        f.write(GetTestData(td_num))
    with open("../test.txt") as f:
        # Start Input code ---------------------------------------
        n,c=map(int,f.readline().split())
        s=[0]*n
        t=[0]*n
        ch=[0]*n
        for i in range(n):
            s[i],t[i],ch[i]=map(int,f.readline().split())
        # End Input code ---------------------------------------
else:
    for i in range(1):
        # Start Input code ---------------------------------------
        n,c=map(int,input().split())
        s=[0]*n
        t=[0]*n
        ch=[0]*n
        for i in range(n):
            s[i],t[i],ch[i]=map(int,input().split())
        # End Input code ---------------------------------------
#print('n,g,p=',n,c,s,t,ch)
table=[[0 for i in range(2*10**5+2)] for j in range(c)]
#print(table)
for i in range(n):
    for j in range(2*s[i]-1,2*t[i]):
        table[ch[i]-1][j]=1
ans=0
for i in range(2*10**5+2):
    tt=0
    for x in range(c):
        tt+=table[x][i]
    ans=max(ans,tt)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import bisect
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, C] = [int(input_raw[0]), int(input_raw[1])]
    dic_s = {}
    dic_t = {}
    max_t = 0
    for i in range(N):
        input_raw = read_func().strip().split()
        [s, t, c] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
        max_t = max(t, max_t)
        if c not in dic_s:
            dic_s[c] = [s]
            dic_t[c] = [t]
        else:
            dic_s[c].append(s)
            dic_t[c].append(t)

    for c in dic_s:
        dic_s[c].sort()
        dic_t[c].sort()

    max_count = 0

    for s in range(1, max_t):
        t = s + 1
        count = 0
        for c in dic_s:
            idx_s = bisect.bisect_left(dic_s[c], t) - 1
            idx_t = bisect.bisect_left(dic_t[c], s)

            if idx_t >= len(dic_t[c]) or idx_s < 0:
                continue
            if dic_s[c][idx_t] <= s or t <= dic_t[c][idx_s]:
                count += 1
        max_count = max(count, max_count)
    print max_count




if __name__ == '__main__':
    main()