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())
l = [[0]*(10**5+5) for _ in range(c)]
for i in range(n):
    s,t,k = map(int,input().split())
    l[k-1][s-1] += 1
    l[k-1][t-1] -= 1
for i in range(c):
    for j in range(1,10**5+2):
        l[i][j] += l[i][j-1]

for i in range(c):
    for j in range(10**5+2):
        if l[i][j] == 0 and l[i][j+1] == 1:
            l[i][j] = 1
ans = 0
for j in range(10**5+1):
    s = 0
    for i in range(c):
        s += l[i][j]
    ans = max(ans,s)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n, c = map(int, input().split())
stc = [[] for i in range(c+1)]
for i in range(n):
  s_, t_, c_ = map(int, input().split())
  stc[c_].append([s_,t_])
  

stc_ = []
for i in range(1, c+1):
    stc[i] = sorted(stc[i], key=lambda x:(x[0], x[1]))
    j = 0
    l = len(stc[i])
    flg = False
    while j < l:
        if not flg:
            cs, ct = stc[i][j][0], stc[i][j][1]
        if j == l-1:
            stc_.append([cs, ct])
            break
        ns, nt = stc[i][j+1][0], stc[i][j+1][1]
        if ct != ns:
            flg = False
            stc_.append([cs, ct])
        else:
            flg = True
            ct = nt
            if j == l - 2:
                stc_.append([cs, ct])
                break
        j += 1
stc_ = sorted(stc_, key=lambda x:(x[0], x[1]))

m = len(stc_)

cnt = np.zeros(10**5+5, dtype=int)
for i in range(m):
    s, t = stc_[i][0]-1, stc_[i][1]
    cnt[s:t] += 1
print(cnt.max())

Submission status: Accepted

Solution code:
class Imos:
    def __init__(self, n):
        self.B = [0] * n
        self.n = n
        from itertools import accumulate
        self.ac = accumulate

    def __call__(self, l, r):
        l, r = max(l, 0), min(r, self.n - 1)
        self.B[l] += 1
        self.B[r + 1] -= 1

    def out(self):
        *res, = self.ac(self.B)
        # self.__init__(self.n)
        return res

from collections import defaultdict
d = defaultdict(list)
imos = Imos(10 ** 5 + 1)

(N, C), *D = [[*map(int, o.split())] for o in open(0)]
for s, t, c in D:
    d[c] += (s, t),
for p in d.values():
    p.sort()
    ps, pt = p[0]
    for s, t in p[1:] + [[0,0]]:
        if pt == s:
            pt = t
        else:
            imos(ps - 1, pt - 1)
            ps, pt = s, t
print(max(imos.out()))

Submission status: Accepted

Solution code:
class Imos:
    def __init__(self, n):
        self.B = [0] * n
        self.n = n
        from itertools import accumulate
        self.ac = accumulate

    def __call__(self, l, r):
        l, r = max(l, 0), min(r, self.n - 1)
        self.B[l] += 1
        if r + 1 != self.n:
            self.B[r + 1] -= 1

    def out(self):
        *res, = self.ac(self.B)
        return res

from collections import defaultdict
d = defaultdict(list)
imos = Imos(10 ** 5 + 1)

(N, C), *D = [[*map(int, o.split())] for o in open(0)]
for s, t, c in D:
    d[c] += (s, t),
for p in d.values():
    p.sort()
    ps, pt = p[0]
    for s, t in p[1:] + [[0,0]]:
        if pt == s:
            pt = t
        else:
            imos(ps - 1, pt - 1)
            ps, pt = s, t
print(max(imos.out()))

Submission status: Accepted

Solution code:
class Imos:
    def __init__(self, n):
        self.B = [0] * n
        self.n = n
        from itertools import accumulate
        self.ac = accumulate

    def __call__(self, l, r):
        l, r = max(l, 0), min(r, self.n - 1)
        self.B[l] += 1
        if r + 1 != self.n:
            self.B[r + 1] -= 1

    def out(self):
        *res, = self.ac(self.B)
        self.__init__(self.n)
        return res

from collections import defaultdict
d = defaultdict(list)
imos = Imos(10 ** 5 + 1)

(N, C), *D = [[*map(int, o.split())] for o in open(0)]
for s, t, c in D:
    d[c] += (s, t),
for p in d.values():
    p.sort()
    ps, pt = p[0]
    for s, t in p[1:] + [[0,0]]:
        if pt == s:
            pt = t
        else:
            imos(ps - 1, pt - 1)
            ps, pt = s, t
print(max(imos.out()))

Submission status: Accepted

Solution code:
A,B=list(map(int,input().split()))
l=[[] for i in range(100001)]
for i in range(A):
   X,Y,Z=list(map(int,input().split()))
   for j in range(X-1,Y):
      l[j].append(Z)
ans=0
for i in l:
   ans=max(ans,len(set(i)))
print(ans)

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
N,C = ma()
nn = 10**5+4
times = [[0 for i in range(nn)] for j in range(C+1)]
for i in range(N):
    s,t,c = ma()
    times[c][s] +=1
    times[c][t] -=1
for c in range(1,C+1):
    for i in range(nn-1):
        times[c][i+1] += times[c][i]

tot = [0 for i in range(nn)]
for c in range(C+1):
    for i in range(nn-1):
        tot[i] += times[c][i]
        if times[c][i] == 0 and times[c][i+1] ==1:
            tot[i] +=1
print(max(tot))

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    n, c = ns()
    l = 10 ** 5
    table = [[0 for _ in range(l + 1)] for __ in range(c)]

    for _ in range(n):
        s, t, ci = ns()
        ci -= 1
        table[ci][s] += 1
        table[ci][t] -= 1

    ans = 0
    tmp = 0
    for i in range(l + 1):
        fin = 0
        for j in range(c):
            if table[j][i] > 0:
                tmp += table[j][i]
            else:
                fin += table[j][i]
        ans = max(ans, tmp)
        tmp += fin
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    n, c = ns()
    l = 10 ** 5
    table = [[0 for _ in range(l + 10)] for __ in range(c)]

    for _ in range(n):
        s, t, ci = ns()
        ci -= 1
        table[ci][s] += 1
        table[ci][t] -= 1

    ans = 0
    tmp = 0
    for i in range(l + 10):
        fin = 0
        for j in range(c):
            if table[j][i] > 0:
                tmp += table[j][i]
            else:
                fin += table[j][i]
        ans = max(ans, tmp)
        tmp += fin
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, C = map(int, input().split())
cq = [[] for _ in range(C)]
stc = [tuple(map(int, input().split())) for _ in range(n)]
stc = sorted(stc, key=lambda x: x[0])

for s, t, c in stc:
    c -= 1
    if cq[c]:
        fs, ft = cq[c][-1]
        if ft != s:
            cq[c].append([s, t])
        else:
            cq[c][-1] = [fs, t]
    else:
        cq[c].append([s, t])

R = [0] * (2*10**5+2)
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: Accepted

Solution code:
import heapq
N, C, *STC = [int(_) for _ in open(0).read().split()]
STC = [(s, t, c) for s, t, c in zip(STC[::3], STC[1::3], STC[2::3])]
STC.sort()
#もしcを映しているテレビがあるならこれにしてしまうのが最適
#cを映しているテレビがないならすでに終わっているテレビのどれかを選ぶ
#どのテレビもすでに映しているなら新しいテレビを追加する

class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_right(self, p, v):  # apply operator from the right side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(dat[p], v)
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_left(self, p, v):  # apply operator from the left side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(v, dat[p])
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        vl = vr = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                vl = f(vl, dat[l])
                l += 1
            if r & 1:
                r -= 1
                vr = f(dat[r], vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)

ti = (10 ** 10, -10 ** 10)
st = SegmentTree([(10 ** 10, i) for i in range(C + 1)], min, ti)
ans = 0
for s, t, c in STC:
    if st.query(c, c + 1)[0] == 10 ** 10:
        t2, c2 = st.query(1, C + 1)
        if t2 < s:
            st.update(c2, (10 ** 10, c2))
        else:
            ans += 1
    st.update(c, (t, c))
print(ans)

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from collections import deque

def main():
	n,c=MI()

	li=[[0]*c for _ in range(10**5+1)]
	#print(li)

	for _ in range(n):
		s,t,cc=MI()
		for i in range(s-1,t):
			li[i][cc-1]=1

	ans=0

	for A in li:
		ans=max(ans,sum(A))
	print(ans)









if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
sch = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
rec = [[0, 0] for _ in range(C+1)]
num_rec = 1

for i in range(N):
    s, t, c = sch[i]
    start = False
    for j in range(1, num_rec + 1):
        if rec[j][0] - int(rec[j][1] == c) < s:
            rec[j] = [t, c]
            start = True
            break
    if not start:
        num_rec += 1
        rec[num_rec] = [t, c]
    
print(num_rec)

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
imos=[[0 for i in range(c)] for j in range(10**5+1)]#1~10**5+1
for i in range(n):
    s,t,_c=map(int,input().split())
    imos[s-1][_c-1]+=1
    imos[t][_c-1]-=1
for i in range(1,10**5+1):
    for j in range(c):
        imos[i][j]+=imos[i-1][j]
imosans=[0]*(10**5+1)
for i in range(10**5+1):
    for j in range(c):
        imosans[i]+=(imos[i][j]>=1)
print(max(imosans))

Submission status: Accepted

Solution code:
imos = [0]*(10**5+2)#0~10**5+1

N,C = map(int,input().split())
C = 30
mitai = [[] for i in range(C+1)]

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

for i in range(C+1):
    mitai[i].sort()


for i in range(C+1):
    preT = -1
    for j in mitai[i]:
        s,t = j[0],j[1]
        if preT == s:
            imos[s+1]+=1
            imos[t+1]-=1
        else:
            imos[s]+=1
            imos[t+1]-=1
        preT = t

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

print(max(imos))

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
a=[]
tf=0
for _ in range(n):
  s,t,ch=map(int,input().split())
  a+=[(ch,s,t)]
a=sorted(a)
flag=a[0][0]
ans=[0]*(10**5+1)
tf=0
for ch,s,t, in a:
  if ch==flag and tf==s:ans[s]+=1
  else:ans[s-1]+=1
  ans[t]-=1
  tf=t
  flag=ch
for i in range(10**5):
  ans[i+1]+=ans[i]
print(max(ans))

Submission status: Accepted

Solution code:
from itertools import accumulate
n, C = map(int, input().split())

U = 10**5
channels = [[0]*(U+1) for _ in range(C)]
for _ in range(n):
    s, t, c = map(lambda x: int(x)-1, input().split())
    channels[c][s] += 1
    channels[c][t] -= 1


for i in range(C):
    for j in range(U):
        channels[i][j+1] += channels[i][j]

schedules = [0]*(U+1)
for i in range(C):
    L = None
    for j in range(U+1):
        if channels[i][j] and L is None:
            L = j-1
            continue

        if not channels[i][j] and L is not None:
            schedules[max(L, 0)] += 1
            schedules[j] -= 1
            L = None

print(max(accumulate(schedules)))

Submission status: Accepted

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

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

Submission status: Accepted

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

def main():
  n,c=map(int,readline().split())
  m=2*10**5
  stc=[list(map(int,l.split())) for l in read().splitlines()]
  cht=np.zeros((c,m+1),dtype='int64')
  for e in stc:
    cht[e[2]-1,2*e[0]-1:2*e[1]]=np.ones(2*e[1]-2*e[0]+1)
  print(max(np.sum(cht,axis=0)))

if __name__=='__main__':
  main()

Submission status: Accepted

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.zeros((c,m+1),dtype='int64')
for e in stc:
  cht[e[2]-1,2*e[0]-1:2*e[1]]=np.ones(2*e[1]-2*e[0]+1)
print(max(np.sum(cht,axis=0)))

Submission status: Accepted

Solution code:
import sys
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=[[0]*(m+1) for _ in range(c)]
for e in stc:
  cht[e[2]-1][2*e[0]-1:2*e[1]]=[1 for _ in range(2*e[1]-2*e[0]+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: Accepted

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

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

count = [0]*(10**5+1)
for i in range(c):
  program[i].sort()
  l = len(program[i])
  judge = True
  for j in range(l-1):
    if judge:
      count[program[i][j][0]-1] += 1
    if program[i][j][1] == program[i][j+1][0]:
      judge = False
    else:
      judge = True
    if judge:
      count[program[i][j][1]] -= 1
  if l == 0:
    continue
  if judge:
    count[program[i][l-1][0]-1] += 1
  count[program[i][l-1][1]] -= 1

ans = 0
for i in range(10**5+1):
  if i != 0:
    count[i] += count[i-1]
  if ans < count[i]:
    ans = count[i]
print(ans)

Submission status: Accepted

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

#tv[i] = [t, c]
tv = [[-1, 0] for i in range(C)]

prog.sort()

for p in prog:
    s, t, c = p
    for i in range(C):
        if tv[i][0] < s - 0.5 or tv[i][1] == c or tv[i][1] == 0:
            tv[i][0] = t
            tv[i][1] = c
            break


ans = 0
for i in range(C):
    if tv[i][0] > 0:
        ans += 1
    else:
        break

print(ans)

Submission status: Accepted

Solution code:
N , C = map(int,input().split())
tel = [[0,-1] for i in range(C)]
pro = [list(map(int,input().split())) for i in range(N)]
pro.sort()
for s , t , c in pro:
    for i in range(C):
        if tel[i][0] < s - 0.5 or tel[i][1] == c or tel[i][1] == -1:
            tel[i][0] = t
            tel[i][1] = c
            break
for i in range(C):
    if tel[i][1] == -1:
        print(i)
        exit()
print(C)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,c=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(n)]

dd=defaultdict(lambda: [0]*(10**5+1))
for s,t,ch in s:
  for i in range(s,t+1):
    dd[ch][i]=1
ans=0
for i in range(10**5+1):
  cnt=0
  for ch in range(c+1):
    if dd[ch][i]==1:
      cnt+=1
  ans=max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, C, *STC = map(int, read().split())

    P = [[] for _ in range(C)]
    for s, t, c in zip(*[iter(STC)] * 3):
        P[c - 1].append((s, t))

    M = 10 ** 5
    vec = [0] * (M + 2)
    for i in range(C):
        P[i].sort()
        for j, (s, t) in enumerate(P[i]):
            if j > 0 and s == P[i][j - 1][1]:
                vec[s] += 1
                vec[t] += -1
            else:
                vec[s - 1] += 1
                vec[t] += -1

    vec = list(accumulate(vec))

    print(max(vec))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

N,C = MI()
A = [[0]*(10**5+2) 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+2):
    ans = max(ans,sum(A[i][j] > 0 for i in range(1,C+1)))

print(ans)

Submission status: Accepted

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

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

stc.sort()

lst = []
hq = [[-1, -1]]
heapq.heapify(hq)
ans = 1
for i in range(N):
    p = stc[i]
    q = heapq.heappop(hq)
    if p[0] < q[0]:
        heapq.heappush(hq, q)

        ans += 1

    elif p[0] == q[0]:
        lst = []
        jdg2 = True

        while p[0] == q[0] and p[2]>= q[1]:
            if p[2] == q[1]:

                jdg2 = False
            else:
                lst.append(q)
            if hq: q = heapq.heappop(hq)
            else: break
        if jdg2:
            ans += 1
        if p[0] != q[0] or p[2] < q[1]:
            heapq.heappush(hq, q)

        for k in lst:
            heapq.heappush(hq, k)

    heapq.heappush(hq, [p[1], p[2]])

print(ans)

Submission status: Accepted

Solution code:
import sys

N, C = map(int, sys.stdin.readline().split())

# 同一チャンネルならtとsが連続していても1台で録画できる
# そのため、通常のimos法ではなく、録画開始・終了のチャンネルを保持する
times = [[set() for _ in range(10**5 + 5)], [set() for _ in range(10**5 + 5)]]
max_t = 0
for _ in range(N):
    s, t, c = map(int, sys.stdin.readline().split())
    # 基本的にs-1だけでよいが、同一チャンネルで録画が連続する場合の対応を入れておく
    times[0][s-1].add(c)
    times[0][s].add(c)
    times[1][t].add(c)
    max_t = max(max_t, t)

ans = 0
recording = set()
for i in range(max_t + 5):
    recording -= times[1][i]
    recording |= times[0][i]
    ans = max(ans, len(recording))

print(ans)

Submission status: Accepted

Solution code:
import itertools
n, c = map(int, input().split())
cs = [[0]*(10**5+10) for _ in range(c+1)]
#cs = [[0]*(15) for _ in range(c+1)]
for i in range(n):
    s, t, ch = map(int, input().split())
    s += 1
    t += 1
    cs[ch][t] = s

for i in range(1,c+1):
    for j in range(1,10**5+10):
    #for j in range(15):
        if cs[i][cs[i][j]] != 0:
            start = cs[i][j]
            cs[i][j] = cs[i][start]
            cs[i][start] = 0

#print(cs)
rsw = [0]*(10**5+10)
#rsw = [0]*(15)
for i in range(1,c+1):
    for j in range(1,10**5+10):
    #for j in range(15):
        if cs[i][j] != 0:
            cs[i][j] -= 1
            rsw[cs[i][j]] += 1
            rsw[j] -= 1

print(max(itertools.accumulate(rsw)))

Submission status: Accepted

Solution code:
N,C=map(int,input().split())
Z=[list(map(int,input().split())) for i in range(N)]
Z.sort()
def judge(x):
  R=[[-1,-1] for i in range(x)]
  for i in range(N):
    for j in range(x):
      if R[j][1]==Z[i][2]:
        R[j][0]=Z[i][1]
        break
      if j==x-1:
        for k in range(x):
          if R[k][0]<Z[i][0]:
            R[k][0]=Z[i][1]
            R[k][1]=Z[i][2]
            break
          if k==x-1:
            return False
  return True

L,R,M=1,C,0
while L!=R:
  M=(L+R)//2
  if judge(M):
    R=M
  else:
    L=max(L+1,M)
print(L)

Submission status: Accepted

Solution code:
import sys
import queue

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def ddd(al, c):
	rcq = queue.PriorityQueue()
	for _ in range(c):
		rcq.put(0)
	for st, ed in al:
		earliest = rcq.get()
		#pa((earliest,st))
		if earliest >= st-0.5:
			return False
		rcq.put(ed)
	return True

def main():
	#a = int(input())
	n, c = tin()
	#s = input()
	dd=[[] for _ in range(c)]
	for _ in range(n):
		s, t, cv = tin()
		dd[cv-1].append((s,t))
	#for cl in dd:
	#	pa(cl)
	
	aal=[]
	for cl in dd:
		if len(cl)==0:
			continue
		cl.sort()
		sa, ta = cl[0]
		for s, t in cl[1:]:
			if ta == s:
				ta = t
			else:
				aal.append((sa, ta))
				sa,ta = s, t
		else:
			aal.append((sa, ta))
			
	#aal = [list(tin()) for _ in range(n)]
	aal.sort()
	#pa(aal)
	for i in range(1, c+1):
		is_ok = ddd(aal, i)
		#pa(i)
		if is_ok:
			return i
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

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

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

print(max([sum(rec[i]) for i in range(10**5)]))

Submission status: Accepted

Solution code:
import sys
from collections import deque
from itertools import accumulate
def input(): return sys.stdin.readline().strip()


def main():
    """
    全部の番組に対して、例えば[2, 4)->[1, 4)のように録画準備時間を確保してたけど、
    同一チャンネルなら、例えば[2, 4), [4, 6)のように続く場合レコーダーは１台で十分。。
    """
    N, C = map(int, input().split())
    channel = [[] for _ in range(C)]
    for _ in range(N):
        s, t, c = map(int, input().split())
        channel[c - 1].append((s, t))
    
    schedule = [0] * (10**5 + 3)
    for c in range(C):
        channel[c].sort()
        channel[c] = deque(channel[c])
        if not channel[c]: continue
        pre_s, pre_t = channel[c].popleft()
        while channel[c]:
            if pre_t == channel[c][0][0]:
                pre_t = channel[c][0][1]
                channel[c].popleft()
                continue
            schedule[pre_s - 1] += 1
            schedule[pre_t] -= 1
            pre_s, pre_t = channel[c].popleft()
        schedule[pre_s - 1] += 1
        schedule[pre_t] -= 1
    total = accumulate(schedule)
    print(max(total))

        
    



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
max_size = 10 ** 5
record_list = [[int(i) - 1 for i in input().split()] for _ in range(N)]
ans_list = [0 for _ in range(max_size)]
for c in range(C):
    T = [0 for _ in range(max_size + 1)]
    for s, t, i in record_list:
        if i == c:
            T[s] += 1
            T[t + 1] -= 1
    for i in range(max_size):
        T[i + 1] += T[i]
    for i in range(max_size):
        ans_list[i] += T[i] > 0
print(max(ans_list))

Submission status: Accepted

Solution code:
# 解説 imos
n, C = map(int, input().split())
L = [tuple(map(int, input().split())) for _ in range(n)]
m = 10 ** 5
S = [0] * m
for i in range(1, C + 1):
    T = [0] * (m + 1)
    for s, t, c in L:
        if c == i:
            T[s - 1] += 1
            T[t] -= 1
    for i in range(m):
        T[i + 1] += T[i]
    for i in range(m):
        S[i] += T[i] > 0
print(max(S))

Submission status: Accepted

Solution code:
# 解説 imos
n, C = map(int, input().split())
L = [tuple(map(int, input().split())) for _ in range(n)]
m = 2 * 10 ** 5 + 2
S = [0] * m
for x in range(1, C + 1):
    T = [0] * m
    for s, t, c in L:
        if c == x:
            # 始点を奇数, 終点を偶数にするのうまい
            T[2 * s - 1] += 1
            T[2 * t] -= 1
    for i in range(1, m):
        T[i] += T[i - 1]
    for i in range(m):
        if T[i] > 0:
            S[i] += 1
print(max(S))

Submission status: Accepted

Solution code:
n, C = map(int, input().split())
L = [tuple(map(int, input().split())) for _ in range(n)]
L.sort()
tmp = [[] for _ in range(C)]
for s, t, c in L:
    if tmp[c - 1]:
        if tmp[c - 1][-1][1] == s:
            tmp[c - 1][-1][1] = t
            continue
    tmp[c - 1].append([s, t])
l = []
for v in tmp:
    for i in v:
        l.append(i)
l.sort()

r = [0] * C
for s, t in l:
    for i in range(C):
        if r[i] < s:
            r[i] = t
            break
print(sum(1 for i in r if i))

Submission status: Accepted

Solution code:
import numpy as np
N, C = map(int, input().split())
s = np.empty(N)
t = np.empty(N)
c = np.empty(N)
for i in range(N):
  s[i], t[i], c[i] =  map(int, input().split())
TimeTable = np.zeros((C,100001))
maxTime = 0
for i in range(N):
  channle = int(c[i] - 1)
  for j in range(int(s[i]),int(t[i])+1):
    TimeTable[channle,j] = 1
  if maxTime < t[i]:
    maxTime = t[i]
MaxRecode = 0
for i in range(int(maxTime)):
  Recode = np.sum(TimeTable[:,i])
  if Recode > MaxRecode:
    MaxRecode = Recode
print(int(MaxRecode))

Submission status: Accepted

Solution code:
n,C=list(map(int,input().split()))
part=[[0]*(3*10**5) for _ in range(31)]
part2=[0]*(3*10**5)

for _ in range(n):
    s,t,c=list(map(int,input().split()))

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

for i in range(1,C+1):
    for j in range(1,10**5+1):
        if part[i][j]==1:
            part2[2*j-1]+=1
        elif part[i][j]==-1:
            part2[2*j]-=1

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

print(ans)