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

TV = sorted(TV, key=lambda x: x[1])

rec = [0] * (10 ** 5 + 1)
cs =  [set() for _ in range(10 ** 5 + 1)]

for s, t, c in TV:
    rec[t] -= 1
    if c not in cs[s]:
        rec[s - 1] += 1
    else:
        rec[s] += 1
    cs[t].add(c)

rec_s = [rec[0]]
for r in rec[1:]:
    rec_s.append(rec_s[-1] + r)

print(max(rec_s))

Submission status: Accepted

Solution code:
n,c = map(int,input().split())
arr = [0 for i in range(10**5+1)]
tv = [[0,0,0] for i in range(n)]
for i in range(n):
    s,t,c = map(int,input().split())
    tv[i][0] = s
    tv[i][1] = t
    tv[i][2] = c

tv.sort(key = lambda x:(x[2],x[0]))
# print(tv)

channel = tv[0][2]
bef = -1
for i in range(n):
    if channel != tv[i][2]:
        channel = tv[i][2]
        bef = -1
        s = tv[i][0]
        e = tv[i][1]
        if bef != s:
            arr[s]+=1
        bef = e
        for j in range(s+1,e+1):
            arr[j] += 1
    else:
        s = tv[i][0]
        e = tv[i][1]
        if bef != s:
            arr[s]+=1
        bef = e
        for j in range(s+1,e+1):
            arr[j] += 1
# print(arr[:13])
print(max(arr))

Submission status: Accepted

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

channels = [[] for _ in range(C)]
maxT = 0

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

maxT = maxT * 2 + 10
tvSum = [0 for _ in range(maxT)]

for tv in channels :
    imos = [0 for _ in range(maxT)]
    for (s, t) in tv :
        imos[s * 2 - 1] += 1
        imos[t * 2] -= 1
    for i in range(1, maxT) :
        imos[i] += imos[i - 1]
    for i in range(maxT) :
        if imos[i] > 0 :
            tvSum[i] += 1

print(max(tvSum))

Submission status: Accepted

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

R = []
for s,t,c in STC:
    i = -1
    tm = 0
    for j,r in enumerate(R):
        tr,cr = r
        if (c==cr and tm<=tr<=s) or (c!=cr and tm<tr<=s-0.5):
            i = j
            tm = tr
    if i==-1:R.append((t,c))
    else:R[i] = (t,c)
print(len(R))

Submission status: Accepted

Solution code:
import numpy as np

import numpy as np

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

Submission status: Accepted

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

tp = defaultdict(list)
i_max = 0
for _ in range(n):
    s, t, c = map(int, input().split())
    tp[c].append([s, t])
    i_max = max(i_max, t+1)

for c in tp:
    tp[c].sort()
    x = [tp[c][0]]
    for i in range(1, len(tp[c])):
        if x[-1][1] == tp[c][i][0]:
            x[-1][1] = tp[c][i][1]
        else:
            x.append(tp[c][i])
    tp[c] = x

r = [0] * (i_max + 5)

for c in tp:
    for s, t in tp[c]:
        r[s] += 1
        r[t+1] -= 1

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

print(ans)

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
stc=[[] for i in range(c+1)]
a=[]
t=0
for i in range(n):
    p=[int(j) for j in input().split()]
    stc[p[2]].append([p[0],p[1]])
    t=max(t,p[1])
ans=10**100
for i in range(c+1):
    p=10**10
    stc[i].sort()
    for j in range(len(stc[i])):
        if j+1<len(stc[i]):
            if stc[i][j][1]==stc[i][j+1][0]:
                if p==10**10:
                    p=stc[i][j][0]
            else:
                if p!=10**10:
                    a.append([p,stc[i][j][1]])
                else:
                    a.append([stc[i][j][0],stc[i][j][1]])
                p=10**10
        else:
            if p!=10**10:
                a.append([p,stc[i][j][1]])
            else:
                a.append([stc[i][j][0],stc[i][j][1]])

table=[0]*(t+1)
for i in range(len(a)):
    table[a[i][0]-1]+=1
    table[a[i][1]]-=1
for i in range(1,t+1):
    table[i]+=table[i-1]

print(max(table))

Submission status: Accepted

Solution code:
N,C=map(int,input().split())
stc=sorted([list(map(int,input().split())) for _ in [0]*N],key=lambda x:x[0])
rokuga=[]
for i in range(N):
    for j,r in enumerate(rokuga):
        if r[0]==stc[i][2]:
            if r[1]<=stc[i][0]:
                rokuga[j][1]=stc[i][1]
                break
    else:
        for j,r in enumerate(rokuga):
            if r[1]<stc[i][0]:
                rokuga[j]=[stc[i][2],stc[i][1]]
                break
        else:
            rokuga.append([stc[i][2],stc[i][1]])
print(len(rokuga))

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
pro=[]
for i in range(c):
    pro.append([])
for i in range(n):
    s,t,c_0=map(int,input().split())
    pro[c_0-1].append((s,t))
Pro=[]
for i in range(c):
    pro[i].sort(reverse=True)
    if pro[i]==[]:
        continue
    pre=pro[i].pop()
    while pro[i]!=[]:
        now=pro[i].pop()
        if pre[1]==now[0]:
            pre=(pre[0],now[1])
        else:
            Pro.append(pre)
            pre=now
    Pro.append(pre)
import heapq
heapq.heapify(Pro)
Used=[]
heapq.heapify(Used)
now=heapq.heappop(Pro)
heapq.heappush(Used,now[1])
ans=1
while len(Pro)!=0:
    now=heapq.heappop(Pro)
    near=heapq.heappop(Used)
    if near<now[0]:
        heapq.heappush(Used,now[1])
    else:
        ans+=1
        heapq.heappush(Used,now[1])
        heapq.heappush(Used,near)
print(ans)

Submission status: Accepted

Solution code:
n,C=[int(i) for i in input().split()]
stc=[[int(i) for i in input().split()] for _ in range(n)]
time=[0]*(2*(10**5+1))
end=[[0]*(10**5+1) for _ in range(C)]   #チャンネル別の終わりの記録

for s,t,c in stc:
    end[c-1][t]+=1

for s,t,c in stc:
    if end[c-1][s]==0:
        time[2*s-1]+=1
    else:
        time[2*s]+=1
    time[2*t]-=1

for i in range(1,2*10**5+2):
    time[i]+=time[i-1]
print(max(time))

Submission status: Accepted

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

program_list = []

for i in range(N):
    s,t,c = list(map(int,input().split()))
    program_list.append((s-0.5,"s",c-1))
    program_list.append((t,"t",c-1))

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

c_list=[0 for i in range(C)]
count_list=[0 for i in range(C)]

max_num=0
for i in range(2*N):
    if program_list[i][1]=="s":
        c = program_list[i][2]
        count_list[c]+=1
        c_list[c] = min(1,count_list[c])
        max_num=max(sum(c_list),max_num)
    else:
        c = program_list[i][2]
        count_list[c]-=1
        c_list[c] = min(1,count_list[c])

print(max_num)

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
channels = [[] for _ in range(C)]
for _ in range(N):
    a, b, c = map(int, input().split())
    channels[c-1].append((a, b))
for c in range(C):
    channels[c].sort()
recorders = [0]*(10**5+2)
for c in channels:
    if c:
        recorders[c[0][0]] += 1; recorders[c[0][1] + 1] -= 1;
        for i in range(1, len(c)):
            if c[i][0] == c[i-1][1]:
                recorders[c[i][0] + 1] += 1; recorders[c[i][1] + 1] -= 1;
            else:
                recorders[c[i][0]] += 1; recorders[c[i][1] + 1] -= 1;
for i in range(1, len(recorders)):
    recorders[i] += recorders[i-1]
print(max(recorders))

Submission status: Accepted

Solution code:
from itertools import accumulate
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, C = map(int, input().split())
TV = dict()
programs = [list(map(int, input().split())) for _ in range(N)]
last_time = max([p[1] for p in programs])
for i in range(1, C+1):
    TV[i] = [0]*(last_time*2+2)

for s, t, c in programs:
    s *= 2
    t *= 2
    TV[c][s] += 1
    TV[c][t+1] -= 1

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

ans = 0
for i in range(last_time*2+1):
    tmp = 0
    for c in range(1, C+1):
        if TV[c][i] > 0:
            tmp += 1
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
arr.append([10**10,10**10,100])
arr=sorted(arr,key=lambda x:x[0])
arr=sorted(arr,key=lambda x:x[2])
job=[[] for _ in range(m+1)]
c=arr[0][2]
ts=arr[0][0]
tt=arr[0][1]
for i in range(1,n+1):
  if c!=arr[i][2]:
    job[c].append([ts,tt])
    ts=arr[i][0]
    tt=arr[i][1]
    c=arr[i][2]
  else:
    if tt==arr[i][0]:
      tt=arr[i][1]
    else:
      job[c].append([ts,tt])
      ts=arr[i][0]
      tt=arr[i][1]
cnt=[0]*(10**5+2)
for tj in job:
  for ts,tt in tj:
    cnt[ts]+=1
    cnt[tt+1]-=1
for i in range(1,10**5+2):
  cnt[i]=cnt[i]+cnt[i-1]
print(max(cnt))

Submission status: Accepted

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

programs.sort()
for i in range(N - 2, -1, -1):
    c0, s0, t0 = programs[i]
    c1, s1, t1 = programs[i + 1]
    if c0 == c1 and t0 == s1 + 1:
        programs[i] = (c0, s0, t1) # merge
        programs[i + 1] = (-1, 0, 0) # delete

acc = [0] * (T_MAX + 1)
for i in range(N):
    _c, s, t = programs[i]
    acc[s] += 1
    acc[t] -= 1
for i in range(T_MAX):
    acc[i + 1] += acc[i]

result = max(acc)
print(result)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

# functions used
r = lambda: sys.stdin.readline().strip() #single: int(r()), line: map(int, r().split())
R = lambda: list(map(int, r().split())) # line: R(), lines: [R() for _ in range(n)]
Rmap = lambda: map(int, r().split())
# set inputs
N, C = R()
STC = [R() for _ in range(N)]
#  0.5sec as one unit
tbl = [[0]*(2*(10**5)+5) for _ in range(C)]

for s, t, c in STC:
    c -= 1
    # if we can record the programms continuously (ver1)
    if tbl[c][2*s] != 0 and tbl[c][2*t-1] != 0:
        tbl[c][2*s] = 0
        tbl[c][2*t-1] = 0
    # if we can record the programms continuously (ver2)
    elif tbl[c][2*s] != 0:
        tbl[c][2*s] += 1
        tbl[c][2*t] -= 1
    # if we can record the programms continuously (ver3)
    elif tbl[c][2*t-1] != 0:
        tbl[c][2*t-1] -= 1
        tbl[c][2*s-1] += 1
    # else:
    else:
        tbl[c][2*s-1] = 1
        tbl[c][2*t] = -1

tbl2 = [list(accumulate(a)) for a in tbl]

ans = max([sum(x) for x in zip(*tbl2)])
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

# functions used
r = lambda: sys.stdin.readline().strip() #single: int(r()), line: map(int, r().split())
R = lambda: list(map(int, r().split())) # line: R(), lines: [R() for _ in range(n)]
Rmap = lambda: map(int, r().split())
# set inputs
N, C = R()
STC = [R() for _ in range(N)]
#  0.5sec as one unit
tbl = [[0]*(2*(10**5)+5) for _ in range(C)]

for s, t, c in STC:
    c -= 1
    tbl[c][2*s-1] += 1
    tbl[c][2*t] -= 1


tbl2 = [list(accumulate(a)) for a in tbl]
for i in range(200002):
     for j in range(C):
         if tbl2[j][i]>1:
          	tbl2[j][i]=1

ans = max([sum(x) for x in zip(*tbl2)])
print(ans)


# tmp = [sum(x) for x in zip(*tbl2)]

# res = 0
# for i in range(200002):
#     cc = 0
#     for j in range(C):
#         if tbl2[j][i]:
#             cc += 1
#     res = max(res, cc)
# print(res)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

# functions used
r = lambda: sys.stdin.readline().strip() #single: int(r()), line: map(int, r().split())
R = lambda: list(map(int, r().split())) # line: R(), lines: [R() for _ in range(n)]
Rmap = lambda: map(int, r().split())
# set inputs
N, C = R()
STC = [R() for _ in range(N)]
#  0.5sec as one unit
tbl = [[0]*(2*(10**5)+5) for _ in range(C)]

for s, t, c in STC:
    c -= 1
    # if we can record the programms continuously (ver1)
    if tbl[c][2*s] == -1:
        tbl[c][2*s] = 0
        tbl[c][2*t] = -1
    # if we can record the programms continuously (ver2)
    elif tbl[c][2*t-1] == 1:
        tbl[c][2*t-1] = 0
        tbl[c][2*s-1] = 1
    # else:
    else:
        tbl[c][2*s-1] = 1
        tbl[c][2*t] = -1

tbl2 = [list(accumulate(a)) for a in tbl]
for i in range(200002):
     for j in range(C):
         if tbl2[j][i]>1:
          	tbl2[j][i]=1

ans = max([sum(x) for x in zip(*tbl2)])
print(ans)

# tmp = [sum(x) for x in zip(*tbl2)]

# res = 0
# for i in range(200002):
#     cc = 0
#     for j in range(C):
#         if tbl2[j][i]:
#             cc += 1
#     res = max(res, cc)
# print(res)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

# functions used
r = lambda: sys.stdin.readline().strip() #single: int(r()), line: map(int, r().split())
R = lambda: list(map(int, r().split())) # line: R(), lines: [R() for _ in range(n)]
Rmap = lambda: map(int, r().split())
# set inputs
N, C = R()
STC = [R() for _ in range(N)]
#  0.5sec as one unit
tbl = [[0]*(2*(10**5)+5) for _ in range(C)]

for s, t, c in STC:
    c -= 1
    # if we can record the programms continuously (ver1)
    if tbl[c][2*s] != 0:
        tbl[c][2*s] += 1
        tbl[c][2*t] -= 1
    # if we can record the programms continuously (ver2)
    elif tbl[c][2*t-1] != 0:
        tbl[c][2*t-1] -= 1
        tbl[c][2*s-1] += 1
    # else:
    else:
        tbl[c][2*s-1] = 1
        tbl[c][2*t] = -1

tbl2 = [list(accumulate(a)) for a in tbl]
for i in range(200002):
     for j in range(C):
         if tbl2[j][i]==2:
          	tbl2[j][i]=1

ans = max([sum(x) for x in zip(*tbl2)])
print(ans)

# tmp = [sum(x) for x in zip(*tbl2)]

# res = 0
# for i in range(200002):
#     cc = 0
#     for j in range(C):
#         if tbl2[j][i]:
#             cc += 1
#     res = max(res, cc)
# print(res)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

# functions used
r = lambda: sys.stdin.readline().strip() #single: int(r()), line: map(int, r().split())
R = lambda: list(map(int, r().split())) # line: R(), lines: [R() for _ in range(n)]
Rmap = lambda: map(int, r().split())
# set inputs
N, C = R()
STC = [R() for _ in range(N)]
#  0.5sec as one unit
tbl = [[0]*(2*(10**5)+5) for _ in range(C)]

for s, t, c in STC:
    c -= 1
    # if we can record the programms continuously (ver1)
    if tbl[c][2*s] != 0:
        tbl[c][2*s] += 1
        tbl[c][2*t] -= 1
    # if we can record the programms continuously (ver2)
    elif tbl[c][2*t-1] != 0:
        tbl[c][2*t-1] -= 1
        tbl[c][2*s-1] += 1
    # else:
    else:
        tbl[c][2*s-1] = 1
        tbl[c][2*t] = -1

tbl2 = [list(accumulate(a)) for a in tbl]
for i in range(200002):
     for j in range(C):
         if tbl2[j][i]>1:
          	tbl2[j][i]=1

ans = max([sum(x) for x in zip(*tbl2)])
print(ans)

# tmp = [sum(x) for x in zip(*tbl2)]

# res = 0
# for i in range(200002):
#     cc = 0
#     for j in range(C):
#         if tbl2[j][i]:
#             cc += 1
#     res = max(res, cc)
# print(res)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

# functions used
r = lambda: sys.stdin.readline().strip() #single: int(r()), line: map(int, r().split())
R = lambda: list(map(int, r().split())) # line: R(), lines: [R() for _ in range(n)]
Rmap = lambda: map(int, r().split())
# set inputs
N, C = R()
STC = [R() for _ in range(N)]
#  0.5sec as one unit
tbl = [[0]*(2*(10**5)+5) for _ in range(C)]

for s, t, c in STC:
    c -= 1
    # if we can record the programms continuously (ver1)
    if tbl[c][2*s] != 0:
        tbl[c][2*s] += 1
        tbl[c][2*t] -= 1
    # if we can record the programms continuously (ver2)
    elif tbl[c][2*t-1] != 0:
        tbl[c][2*t-1] -= 1
        tbl[c][2*s-1] += 1
    # else:
    else:
        tbl[c][2*s-1] = 1
        tbl[c][2*t] = -1

tbl2 = [list(accumulate(a)) for a in tbl]

# ans = max([sum(x) for x in zip(*tbl2)])
# print(ans)

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

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

# functions used
r = lambda: sys.stdin.readline().strip() #single: int(r()), line: map(int, r().split())
R = lambda: list(map(int, r().split())) # line: R(), lines: [R() for _ in range(n)]
Rmap = lambda: map(int, r().split())
# set inputs
N, C = R()
STC = [R() for _ in range(N)]
#  0.5sec as one unit
tbl = [[0]*(2*(10**5)+5) for _ in range(C)]

for s, t, c in STC:
    c -= 1
    # if we can record the programms continuously (ver1)
    if tbl[c][2*s] != 0:
        tbl[c][2*s] += 1
        tbl[c][2*t] -= 1
    # if we can record the programms continuously (ver2)
    elif tbl[c][2*t-1] != 0:
        tbl[c][2*t-1] -= 1
        tbl[c][2*s-1] += 1
    # else:
    else:
        tbl[c][2*s-1] = 1
        tbl[c][2*t] = -1

tbl2 = [list(accumulate(a)) for a in tbl]

# ans = max([sum(x) for x in zip(*tbl2)])
# print(ans)

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

Submission status: Accepted

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

st_concat = [[] for _ in range(C)]
for c in range(C):
    if len(st[c]) != 0:
        s0,t0 = st[c].pop()
        while st[c]:
            s,t = st[c].pop()
            if t != s0:
                st_concat[c].append([s0,t0])
                s0,t0 = s,t
            else:
                s0 = s
        st_concat[c].append([s0,t0])

for c in range(C):
    for s,t in st_concat[c]:
        cum[s-1] += 1
        cum[t] -= 1

for i in range(10**5):
    cum[i+1] += cum[i]
print(max(cum))

Submission status: Accepted

Solution code:
# using main() makes code faster from the point of view of "access to variables in global name-space"
# def main():

# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
from math import factorial
def combinations_count(n, r):
    # faster than the following code
    # def combinations_count(n, r):
    #     return factorial(n) // (factorial(n - r) * factorial(r))
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from operator import itemgetter 
# ex1: List.sort(key=itemgetter(1))
# ex2: sorted(tuples, key=itemgetter(1,2))
from functools import reduce
from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)

# first create factorial_list
# fac_list = mod_factorial_list(n)
INF = 10 ** 18
MOD = 10 ** 6 + 3
modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
def modinv(a, p = MOD):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))


# initialize variables and set inputs
#initialize variables
    # to initialize list, use [0] * n
    # to initialize two dimentional array, use [[0] * N for _ in range(N)]
# set inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
# calculate and output
    # output pattern
    # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6

# set test data
# sys.stdin = open('sample.txt') # for test

# functions used
r = lambda: sys.stdin.readline().strip() #single: int(r()), line: map(int, r().split())
R = lambda: list(map(int, r().split())) # line: R(), lines: [R() for _ in range(n)]
Rmap = lambda: map(int, r().split())
# set inputs
N, C = R()
STC = [R() for _ in range(N)]
tbl = [[0]*(2*(10**5)+5) for _ in range(C)]

# watch out: join tv programmes which are continuously broadcast in one channel
for s, t, c in STC:
    c -= 1
    if tbl[c][2*s] != 0:
        tbl[c][2*s] += 1
        tbl[c][2*t] -= 1
    elif tbl[c][2*t-1] != 0:
        tbl[c][2*t-1] -= 1
        tbl[c][2*s-1] += 1
    else:
        tbl[c][2*s-1] = 1
        tbl[c][2*t] = -1
# for s, t, c in STC:
#     c -= 1
#     if tbl[c][s] == -1:
#         tbl[c][s] = 0
#         tbl[c][t] = -1
#     elif tbl[c][t-1] == 1:
#         tbl[c][s-1] = 1
#         tbl[c][t-1] = 0
#     else:
#         tbl[c][s-1] = 1
#         tbl[c][t] = -1

tbl2 = [list(accumulate(a)) for a in tbl]
# ans = max([sum(x) for x in zip(*tbl2)])
# print(ans)

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

# if __name__ == '__main__':
#     main()

Submission status: Accepted

Solution code:
from functools import reduce
import math
import collections

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]
    N_max = 100005
    N, C = (int(_) for _ in input().split())
    s = []
    t = []
    c = []
    for i in range(N):
        s1, s2,s3 = (int(_) for _ in input().split())
        s.append(s1)
        t.append(s2)
        c.append(s3)
        
    d = [[0 for j in range(C)] for i in range(N_max)]
    for i in range(N):
        for j in range(s[i]-1,t[i]):
            d[j][c[i]-1] = 1
    ans = 0
    for i in range(N_max):
        ans = max(sum(d[i]),ans)
    print(ans)
    # for i in range(N):
    #     for d_i in range(len(d)):
    #         can_insert_channel = True
    #         for d_j in range(s[i],t[i]+1):
    #             if d_j == s[i]:
    #                 if d[d_i][d_j] == c[i] or d[d_i][d_j] == 0:
    #                     continue
    #                 else:
    #                     can_insert_channel = False
    #                     break
    #             if d[d_i][d_j] != 0:
    #                 can_insert_channel = False
    #                 break
                
    #         if can_insert_channel:
    #             for j in range(s[i],t[i]+1):
    #                 d[d_i][j] = c[i]
    #             break
    #         elif d_i == len(d)-1:
    #             d.append([0]*N_max)
    #             for j in range(s[i],t[i]+1):                    
    #                 d[d_i+1][j]= c[i]
    # for i in range(len(d)):
    #     print(list(d[i]))
    # print(len(d))
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
from itertools import accumulate as acc

input=sys.stdin.readline

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


a=[[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,input().split())
    recs,rect=a[c][s],a[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

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

print(max(list(acc(rec))))

Submission status: Accepted

Solution code:
import sys
import math
from itertools import accumulate as acc

input=sys.stdin.readline

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


a=[[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,input().split())
    recs,rect=a[c][s],a[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

    a[c][s],a[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:
import sys
import math
from itertools import accumulate as acc

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


a=[[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,input().split())
    recs,rect=a[c][s],a[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

    a[c][s],a[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 = list(map(int, input().split()))
stc = [list(map(int, input().split())) for _ in range(N)]

E = max(stc, key = lambda x: x[1])[1]

R = {}
stc.sort()
L = [0] * (E + 1)
for s, t, c in stc:
  if c not in R:
    R[c] = t
  else:
    if R[c] == s:
      s += 1
    R[c] = t
  L[s - 1] += 1
  L[t] -= 1

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

print(ans)

Submission status: Accepted

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

res = 0
st = [(0,0)]*30
for s,t,c in inl:
    nx = (t,c)
    cnt = 0
    for i, (t1, c1) in enumerate(st):
        if not (t1 == s and c == c1) and t1 >= s:
            st[i] = (t1,c1)
        else:
            st[i] = nx
            nx = (0, 0)

        if st[i][0] != 0:
            cnt += 1
    res = max(cnt, res)

print(res)

Submission status: Accepted

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

res = 0
st = set()
for s,t,c in inl:
    nx = set()
    for t1, c1 in st:
        if not (t1 == s and c == c1) and t1 >= s:
            nx.add((t1,c1))
    nx.add((t,c))
    st = nx
    res = max(len(nx), res)

print(res)

Submission status: Accepted

Solution code:
import heapq

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

inl = [tuple(map(int, input().split())) for i in range(N)]
inl.sort()

heap = []
res = 0

st = set()
for s,t,c in inl:
    nx = set()
    for t1, c1 in st:
        if t1 == s and c == c1:
            # do nothing
            nx.add((t,c))
        elif t1 >= s:
            nx.add((t1,c1))
    nx.add((t,c))
    st = nx
    res = max(len(nx), res)

print(res)