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:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N,C = map(int,input().split())
time = [0]*(100009*2)
channel = [[0]*(100009*2) for _ in range(C)]
#(方針)チャンネル関係なしに
#同じチャンネルの連続だと録画開始時間に0.5秒のロスがない
# 同チャンネルで 1-7 7-8 → [0.5,8) → 録画機1つ(0.5~7.99) 
# 違うチャンネルで 1-7 7-8 → [0.5,7) 0.5~6.99 , [6.5,8) 6.5~7.99 → 録画機2つ

#前処理:　同チャンネル#0.5が扱いずらいので,sを2s-1,tを2tに対応させる
#ex: 1-3 → 0.5-3 → 1-6
#ex: 3-5 → 2.5-5 → 5-10
#ex: 1-3,3-5 → 1-6,5-10 → 2個必要の区間をつなげる(ex. 1-7 7-8 → 1-8）
max_num = 0
for i in range(N):
 s,t,c = map(int,input().split())
 s,t = 2*s-1,2*t 
 if(channel[c-1][s-1] == 1): channel[c-1][s-1] = 0
 else: channel[c-1][s] = 1
 channel[c-1][t] = 1
 max_num = max(max_num,t)

#imos法
#0.5が扱いずらいので,sを2s-1,tを2tに対応させる
#ex: 1-3 → 0.5-3 → 1-6
#ex: 3-5 → 2.5-5 → 5-10
#ex: 1-3,3-5 → 1-6,5-10 → 2個必要
#A = []
tmp = 0
for i in range(C):
 for j in range(max_num+10):
  if((tmp == 0)and(channel[i][j] == 1)):
    tmp = 1
    a = j
  elif((tmp == 1)and(channel[i][j] == 1)):
    tmp = 0
    b = j
    #A.append([a,b])
    time[a] += 1
    time[b+1] -= 1
#print(A)
    
ans = 0
for i in range(max_num+10):
  if(i != 0): time[i] += time[i-1]
  ans = max(ans,time[i])
print(ans)
#print(time)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left
import random
from itertools import permutations, accumulate, combinations
import sys
import string


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 10 ** 9 + 7


n, c = LI()
L = [0] * (10 ** 5 + 2)
each_channel = [[] for _ in range(c)]
for s, t, k in LIR(n):
    each_channel[k - 1] += [(s, t)]



for i in each_channel:
    i.sort()


for i in range(c):
    pre_t = -1
    for j in range(len(each_channel[i])):
        s, t = each_channel[i][j]
        if j >= 1 and pre_t == s:
            L[pre_t + 1] += 1
            L[t + 1] -= 1
        else:
            L[s] += 1
            L[t + 1] -= 1
        pre_t = t


print(max(accumulate(L)))

Submission status: Accepted

Solution code:
n,c = map(int,input().split())
program = [list(map(int,input().split())) for i in range(n)]
time = [0 for i in range(10**5+1)]

program.sort()
program.sort(key = lambda x: x[2])

for i in range(1,n):
    if program[i][2]==program[i-1][2] and program[i][0]==program[i-1][1]:
        program[i][0] = program[i-1][0]
        program[i-1][0] = None

for i in range(n):
    if program[i][0] == None:
        continue
    time[program[i][0]-1] += 1
    time[program[i][1]] -= 1

count = 0
max_count = 0

for i in range(10**5+1):
    count += time[i]
    max_count = max(max_count,count)

print(max_count)

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
t=[[0]*10**5 for i in range(c)]
for i in range(n):
	a,b,c=map(int,input().split())
	t[c-1][a-1:b]=[1]*(b-a+1)
print(max(map(sum,zip(*t))))

Submission status: Accepted

Solution code:
N,C = map(int,input().split())
ST = []
for _ in range(N):
  s,t,c = map(int,input().split())
  ST.append([s,0,c])
  ST.append([t,1,c])
ST.sort(key=lambda x:x[0])
ST.sort(key=lambda x:x[2])
for i in range(len(ST)-1):
  if ST[i][2]==ST[i+1][2] and ST[i][0]==ST[i+1][0]:
    ST[i][1]=2
    ST[i+1][1]=2

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

ans =[0]
for st in ST:
  if st[1]==0:
    ans.append(ans[-1]+1)
  elif st[1]==1:
    ans.append(ans[-1]-1)
print(max(ans))

Submission status: Accepted

Solution code:
from itertools import accumulate

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

channels = [[0]*(10**5+1) for _ in range(C)]
for s, t, c in STC:
    # print((s, t))
    s, t, c = s-1, t-1, c-1
    channels[c][s] += 1
    channels[c][t] -= 1
all_channels = [0]*(10**5+1)
for channel in channels:
    # print(channel)
    for j, x in enumerate(channel):
        if x == 1:
            all_channels[j] += 1
        if x == -1:
            all_channels[j+1] -= 1 


a = list(accumulate(all_channels))
# print(a)

print(max(a))

Submission status: Accepted

Solution code:
from operator import itemgetter
N,C = [int(x) for x in input().split()]
# list(time,action,channel) action = start:1, stop:0
actions = []
for _ in range(N):
    s,t,c = [int(x) for x in input().split()]
    actions.append((s-0.5, 1, c))
    actions.append((t, 0, c))
actions.sort(key=itemgetter(0))

cnt_now_rec = 0
# list to know the start time of rec. if channel not in rec, takes -1.
channel_now_rec = [-1] * (C+1)
ans = 0
for time,action,channel in actions:
    if(action == 1):
        if(channel_now_rec[channel]==-1):
            cnt_now_rec += 1
        channel_now_rec[channel] = time
    elif(action == 0):
        if(time == channel_now_rec[channel]+0.5):
            pass
        else:
            cnt_now_rec -= 1
            channel_now_rec[channel] = -1
    ans = max(ans,cnt_now_rec)
print(ans)

Submission status: Accepted

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

def main():
    N, C = map(int, input().split())
    stc = sorted([list(map(int, input().split())) for i in range(N)], key=lambda x: (x[2], x[0])) + [[1, 1, 31]]
    # print(stc)
    imos = [0] * (int(1e5) + 10)
    s, t, c = stc[0]
    pre_s, pre_t, pre_c = s, t, c
    for i in range(1, N+1):
        s, t, c = stc[i]
        if c == pre_c and pre_t == s:
            pre_t = t
        else:
            imos[pre_s] += 1
            imos[pre_t + 1] -= 1
            pre_s, pre_t, pre_c = s, t, c
    # print(imos[:100])

    ans = 0
    tmp = 0
    for i in imos:
        tmp += i
        ans = max(ans, tmp)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
T_max = 10**5
N, C = map(int, input().split())
channel = [[] for _ in range(C)]
time = [0]*(T_max+2)
for i in range(N):
    s, t, c = map(int, input().split())
    channel[c-1].append((s, t))
for c in channel:
    c.sort()
    if len(c)==0:
        continue
    time[c[0][0]]+=1
    for i in range(1, len(c)):
        if c[i-1] [1] != c[i][0]:
            time[c[i-1][1]+1] -= 1
            time[c[i][0]]+=1
    time[c[-1][1]+1]-=1
for i in range(1, T_max+1):
    time[i] = time[i-1]+time[i]
print(max(time))

Submission status: Accepted

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

def getlist():
	return list(map(int, input().split()))

#初期化
N, C = getlist()
Lis = [[0 for i in range(10 ** 5 + 3)] for j in range(C)]
for i in range(N):
	s, t, c = getlist()
	Lis[c - 1][s] += 1
	Lis[c - 1][t] -= 1

#計算
for j in range(C):
	v = "x"
	for i in range(10 ** 5 + 1):
		if Lis[j][i] == 1:
			v = "o"
			Lis[j][i] = "o"
		elif Lis[j][i] == 0:
			Lis[j][i] = v
		elif Lis[j][i] == -1:
			Lis[j][i] = "o"
			v = "x"

ans = 0
for i in range(10 ** 5 + 1):
	val = 0
	for j in range(C):
		if Lis[j][i] == "o":
			val += 1
	ans = max(ans, val)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

record = [[0] * 10 ** 5 for _ in range(C)]
for s, t, c in stc:
    for i in range(s, t + 1):
        record[c-1][i-1] = 1

ans = 0
for i in range(10 ** 5):
    cnt = 0
    for j in range(C):
        cnt += record[j][i]
    ans = max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
L=[[0 for i in range(10**5+1)] for i in range(c)]
for i in range(n):
  for j in range(l[i][0],l[i][1]+1):
    L[l[i][2]-1][j]=1
ans=[]
for i in range(10**5+1):
  ct=0
  for j in range(c):
    ct+=L[j][i]
    ans.append(ct)
print(max(ans))

Submission status: Accepted

Solution code:
n, c = map(int, input().split())
MAX_COLS = 10**5
table = [[0 for _ in range(MAX_COLS)] for _ in range(c)]

for _ in range(n):
    s, t, i = list(map(int, input().split()))
    for j in range(max(0, s - 2), t - 1):
        table[i - 1][j] = 1

res = 0
for j in range(MAX_COLS):
    count = 0
    for i in range(c):
        count += table[i][j]
    res = max(res, count)
print(res)

Submission status: Accepted

Solution code:
n, c = map(int, input().split())
MAX_COLS = 10**5
table = [[0 for _ in range(MAX_COLS)] for _ in range(c)]

for _ in range(n):
    s, t, i = list(map(int, input().split()))
    for j in range(s - 1, t - 1):
        table[i - 1][j] = 1

for i in range(c):
    for j in range(MAX_COLS - 1):
        if table[i][j] == 0 and table[i][j + 1] == 1:
            table[i][j] = 1

res = 0
for j in range(MAX_COLS):
    count = 0
    for i in range(c):
        count += table[i][j]
    res = max(res, count)
print(res)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    N,C = map(int,input().split())
    STC = []
    B = [[0]*(10**5+1) for _ in range(C)]
    for i in range(N):
        s,t,c = map(int,input().split())
        for j in range(s,t+1):
            B[c-1][j] = 1
    
    x = 0
    flag = 1
    nowc = -1
    while flag == 1:
        flag = 0
        x += 1
        nowc = -1
        for i in range(1,10**5+1):
            if nowc != -1:
                if B[nowc][i] == 1:
                    B[nowc][i] = 0
                else:
                    nowc = -1
                    for j in range(C):
                        if B[j][i] == 1:
                            nowc = j
                            B[j][i] = 0
                            break
            else:
                for j in range(C):
                    if B[j][i] == 1:
                        flag = 1
                        nowc = j
                        B[j][i] = 0
                        break
    print(x-1)

main()

Submission status: Accepted

Solution code:
import numpy as np

n,c = map(int,input().split())
table = np.zeros(10**5+2, dtype=np.int32)
chs = [[] for _ in range(c+1)]

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

# 同チャンネル内の連続番組を合体
times = []
for ch in chs:
    if not ch: continue
    ch.sort()
    for i in range(len(ch)):
        if i == 0: continue
        if ch[i-1][1] == ch[i][0]:
            ch[i] = [ch[i-1][0], ch[i][1]]
            ch[i-1] = []
    for arr in ch:
        if not arr: continue
        times.append(arr)

# いもす法
for arr in times:
    table[arr[0]] += 1
    table[arr[1]+1] -= 1

# 累積和の最大値
ans = table.cumsum().max()

print(ans)

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
A=[]
for i in range(n):
  s,t,c=map(int,input().split())
  A.append((s,t,c))
A.sort(key=lambda x:(x[2],x[0],x[1]))
B=[]
s,t,c=A[0]

for i in range(1,n):
  s2,t2,c2=A[i]
  if c==c2 and t==s2:
    t=t2
  else:
    B.append((s-1,t,c))
    s,t,c=s2,t2,c2
B.append((s-1,t,c))

T=[0]*(10**5+1)
for s,t,c, in B:
  T[s]+=1
  T[t]-=1
for i in range(10**5):
  T[i+1]+=T[i]
print(max(T))

Submission status: Accepted

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

def inc(n):
  return n+1
def dec(n):
  return n-1

history = {}
for i in range(N):
  s,t,c = map(int,input().split())
  s *= 2
  t *= 2
  #print(history)
  if (t-1) in history and c in history[t-1]:
    history[t-1].pop(c)
  else:
    if t in history:
      history[t][c] = dec
    else:history[t] = {c:dec}
  if (s) in history and c in history[s]:
    history[s].pop(c)
  else:
    #history[s-0.5][c] = inc
    if s-1 in history:
      history[s-1][c] = inc
    else:
      history[s-1] = {c:inc}
maximum = 0
counter = 0
for i in range(100000*2):
  if i in history:
    for func in history[i].values():
      counter = func(counter)
    if counter > maximum:
      maximum = counter
#print(history)
print(maximum)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import accumulate

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

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

    imos = [0] * (10**5 + 1)
    for c, p in programs.items():
        p.sort()
        # チャンネルごとに連結処理を行う
        ps, pt = p[0]
        for s, t in p[1:]:
            if pt == s:
                pt = t
            else:
                imos[ps - 1] += 1
                imos[pt] -= 1
                ps, pt = s, t

        imos[ps - 1] += 1
        imos[pt] -= 1

    print(max(accumulate(imos)))

main()

Submission status: Accepted

Solution code:
n,c = map(int,input().split())
l = [list() for _ in range(c+1)]
for _ in range(n):
  s,t,ch = map(int,input().split())
  l[ch].append((s,t))
al = list()
for x in l:
  x.sort()
for i in range(c+1):
  if l[i] == []:
    continue
  t = list()
  for j in range(len(l[i])-1):
    if l[i][j][1] == l[i][j+1][0]:
      l[i][j+1] = (l[i][j][0],l[i][j+1][1])
    else:
      t.append(l[i][j])
  t.append(l[i][-1])
  al += t
tl = [0]*(10**5+10)
for s,t in al:
  tl[s] += 1
  tl[t+1] -= 1
for i in range(10**5+9):
  tl[i+1] += tl[i]
print(max(tl))

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
stc = [[int(i) for i in input().split()] for _ in range(N)]
stc.append([float('inf')] * 3)

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

imos = [0] * (10 ** 5 + 2)
ps, pt, pc = stc[0]
for i in range(1, N + 1) :
    if stc[i][0] == pt and stc[i][2] == pc :
        pt = stc[i][1]
    else :
        imos[ps] += 1
        imos[pt+1] -= 1
        ps, pt, pc = stc[i]
    
for i in range(1, 10 ** 5 + 2) :
    imos[i] += imos[i-1]

print(max(imos))

Submission status: Accepted

Solution code:

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

slis = [0] * (10 ** 5 + 1)
tlis = [0] * (10 ** 5 + 1)

ans = 0

cs = []
ct = []
for i in range(31):
    cs.append([0] * (10 ** 5 + 1))
    ct.append([0] * (10 ** 5 + 1))

for i in range(N):

    s,t,c = map(int,input().split())

    if ct[c][s] > 0:
        ct[c][s] -= 1
    else:
        cs[c][s] += 1

    if cs[c][t] > 0:
        cs[c][t] -= 1
    else:
        ct[c][t] += 1

for i in range(31):

    for j in range(10 ** 5 + 1):

        slis[j] += cs[i][j]
        tlis[j] += ct[i][j]

now = 0
for i in range(10 ** 5):

    i += 1
    now += slis[i]
    now -= tlis[i-1]
    ans = max(ans,now)

print (ans)

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
MAX = 10**5
s_list = [[] for _ in range(MAX+1)]
t_list = [[] for _ in range(MAX+1)]
for _ in range(N):
  s, t, c = map(int, input().split())
  s_list[s].append(c)
  t_list[t].append(c)
cnt = 0
ans = 0
before = 0
for i in range(MAX+1):
  if before != 0:
    cnt -= before
    before = 0
  for s in s_list[i]:
    cnt += 1
  for t in t_list[i]:
    if not t in s_list[i]:
      before +=1
    cnt -= 1
  cnt += before
  ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n,c = inpl()
s = [inpl() for i in range(n)]
s.sort()
rec = [[0,0]]
for i in range(n):
    flag = False
    for j in range(len(rec)):
        if s[i][0] > rec[j][0] or s[i][2] == rec[j][1]:
            rec[j] = [s[i][1],s[i][2]]
            flag = True
            break
    if flag == False:
        rec.append([s[i][1],s[i][2]])
print(len(rec))

Submission status: Accepted

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

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

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

#print(STC)

import heapq
h = []
for s, t, c in STC:
    heapq.heappush(h, (s-0.5, 0, c))
    heapq.heappush(h, (t, 1, c))

ans = 0
cnt = 0
rec = [0] * (C+1)
while h:
    t, flag, c = heapq.heappop(h)
    if flag == 0:
        if rec[c] == 0:
            rec[c] += 1
            cnt += 1
        else:
            rec[c] += 1
    else:
        rec[c] -= 1
        if rec[c] == 0:
            cnt -= 1
        else:
            pass
        
    ans = max(ans, cnt)
print(ans)

Submission status: Accepted

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


all = []
for ch in range(1, c+1):
    org[ch].sort()
    m = len(org[ch])
    for i in range(m):
        s, t = org[ch][i]
        
        if i == 0:
            pre_s, pre_t = s, t
        else:
            if pre_t == s:
                pre_t = t
            else:
                all.append((2*pre_s-1, 2*pre_t))
                pre_s, pre_t = s, t
            
        if i == m-1:
            all.append((2*pre_s-1, 2*pre_t))


time = [0]*(2*10**5+2)
for l, r in all:
    time[l] += 1
    time[r+1] -= 1
for i in range(2*10**5+1):
    time[i+1] += time[i]

print(max(time))

Submission status: Accepted

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


all = []
for ch in range(1, c+1):
    org[ch].sort()
    m = len(org[ch])
    for i in range(m):
        s, t = org[ch][i]
        if i == 0:
            pre_s, pre_t = s, t
            if i == m-1:
                all.append((2*pre_s-1, 2*pre_t))
        else:
            if pre_t == s:
                pre_t = t
            else:
                all.append((2*pre_s-1, 2*pre_t))
                pre_s, pre_t = s, t
            
            if i == m-1:
                all.append((2*pre_s-1, 2*pre_t))


time = [0]*(2*10**5+2)
for l, r in all:
    time[l] += 1
    time[r+1] -= 1
for i in range(2*10**5+1):
    time[i+1] += time[i]

print(max(time))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC80 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,C = LI()
cha = [[] for _ in range(C)]
ans = 0
lst = [0]*(10**5+2)
for _ in range(n):
    s,t,c = LI()
    cha[c-1].append([s,t])
for i in range(C):
    if len(cha[i]) == 0:
        continue
    cha[i].sort(key = itemgetter(0))
    s,t = cha[i][0]
    tmp = []
    for j in range(1,len(cha[i])):
        if t == cha[i][j][0]:
            t = cha[i][j][1]
        else:
            tmp.append([s,t])
            s,t = cha[i][j]
    tmp.append([s,t])
    for i,j in tmp:
        lst[i] += 1
        lst[j+1] -= 1
lst = list(accumulate(lst))
print(max(lst))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify
from collections import defaultdict

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

d = defaultdict(list)
for _ in range(N):
    s, t, c = tuple(map(int, input().split()))
    d[c].append((s, t))
stc = list()
for c, lst in d.items():
    if len(lst) == 1:
        s, t = lst[0]
        stc.append((s, t, c))
        continue
    lst.sort()
    s0, t0 = lst[0]
    i = 1
    while i < len(lst):
        s1, t1 = lst[i]
        if t0 == s1:
            t0 = t1
            if i == len(lst) - 1:
                stc.append((s0, t0, c))
        else:
            stc.append((s0, t0, c))
            s0 = s1
            t0 = t1
        i += 1

heapify(stc)
end = []
ans = 0
while len(stc) > 0:
    s, t, c = heappop(stc)
    if len(end) > 0:
        endtime = heappop(end)
        if endtime >= s:
            heappush(end, endtime)
    heappush(end, t)
    ans = max(ans, len(end))
print(ans)

Submission status: Accepted

Solution code:
N, C = map(int, input().split())
stcs = []
for i in range(N):
  s, t, c = map(int, input().split())
  stcs.append((s, t, c))
stcs.sort()
rs = []
for s, t, c in stcs:
  ok = False
  for l in rs:
    s0, t0, c0 = l[-1]
    if t0 < s or (t0 == s and c0 == c):
      l.append((s, t, c))
      ok = True
      break
  if not(ok):
    l = [(s, t, c)]
    rs.append(l)
#print(rs)
r = len(rs)
print(r)

Submission status: Accepted

Solution code:
from heapq import *
from itertools import accumulate as ac
n,c=map(int,input().split())
a=sorted([list(map(int,input().split()))for i in range(n)])
b=[[]for i in range(c+1)]
for i,j,h in a:
    if len(b[h])>0:
        if b[h][-1][1]==i:
            b[h][-1][1]=j
        else:
            b[h].append([i,j])
    else:
        b[h].append([i,j])
s=[0]*(2*10**5+2)
for i in b:
    for h,w in i:
        s[2*h-1]+=1
        s[2*w+1]-=1
print(max(list(ac(s))))

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
l=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:[x[2],x[0]])
m=[l[0]]
for i in range(1,n):
    if l[i][2]==m[-1][2] and l[i][0]==m[-1][1]:
        m.append([m.pop()[0],l[i][1],l[i][2]])
    else:m.append(l[i])
for x in m:
    x[0]-=1
ans=[0]*max(x[1] for x in m)
for x in m:
    for i in range(x[0],x[1]):
        ans[i]+=1
print(max(ans))

Submission status: Accepted

Solution code:


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

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

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

merged_channels = [[]for i in range(C)]
for i in range(len(channels)):
    channels[i].sort()
    if len(channels[i])>0:
        merged_channels[i].append(channels[i][0])
        for j in range(1,len(channels[i])):
            if merged_channels[i][-1][1]==channels[i][j][0]:
                merged_channels[i][-1][1] = channels[i][j][1]
            else:
                merged_channels[i].append(channels[i][j])

tv = [0]*(10**5+1)
for i in range(len(merged_channels)):
    for s,t in merged_channels[i]:
        for k in range(s,t+1):
            tv[k]+=1

print(max(tv))

Submission status: Accepted

Solution code:
N,C  = map(int, input().split())
t_max = 2*10**5
c_imos = [[0]*t_max for t in range(C)]
# 前処理 : 同一チャンネルのときはくっつけられる
c_imos = [[0]*t_max for t in range(C)]

for i in range(N):
    s,t,c = map(int, input().split())
    c -= 1
    s -= 1
    # t -= 1
    c_imos[c][s] += 1
    c_imos[c][t] -= 1
    
ans = [0] * t_max
from itertools import accumulate
for c_ in c_imos:
    acc = list(accumulate(c_))
    ans = [a+min(1,b) for a,b in zip(ans,acc)]
print(max(ans))

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC80 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,C = LI()
stc = [LI() for _ in range(n)]
L = []
for i in range(C):
    lst = []
    for j in range(n):
        s,t,c = stc[j]
        if i+1 == c:
            lst.append([s,t])
    lst.sort(key = itemgetter(0))
    lst2 = []
    j = 0
    while j < len(lst):
        if j < len(lst)-1:
            if lst[j][1] == lst[j+1][0]:
                lst2.append((lst[j][0],lst[j+1][1]))
                j += 2
                continue

        lst2.append(tuple(lst[j]))
        j += 1
    L.append(lst2)
x = [[0]*100002 for _ in range(C)]
for i in range(C):
    for j,k in L[i]:
        x[i][j] += 1
        x[i][k+1] -= 1
    x[i] = list(accumulate(x[i]))
ans = 0
for i in range(1,10**5+1):
    s = 0
    for j in range(C):
        if x[j][i] == 1:
            s += 1
    ans = max(ans,s)
print(ans)

Submission status: Accepted

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

from heapq import heappop, heappush

def main():
  n, c = map(int, input().split())
  stc = []
  for _ in range(n):
    stc.append(tuple(map(int, input().split())))
  stc = list(sorted(stc, key=lambda x: (x[2], x[0])))
  restc = []
  prev = stc[0]
  for _stc in stc[1:]:
    if prev[2] == _stc[2] and prev[1] == _stc[0]:
      prev = (prev[0], _stc[1], prev[2])
    else:
      restc.append(prev)
      prev = _stc
  restc.append(prev)

  ans = 0
  th = []
  for _stc in sorted(restc):
    if not th:
      heappush(th, _stc[1])
      if ans == 0:
        ans = 1
    else:
      _th = heappop(th)
      if _th < _stc[0]:
        heappush(th, _stc[1])
      else:
        heappush(th, _th)
        heappush(th, _stc[1])
        ans = max(ans, len(th))
  print(ans)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from itertools import accumulate

N, C = map(int, input().split())
E = [[0] * 100010 for _ in range(C)]
for _ in range(N):
    s, t, c = map(int, input().split())
    E[c-1][s-1] += 1
    E[c-1][t-1] -= 1
F = [0] * 100010
for e in E:
    for i, v in enumerate(e):
        if v == 1:
            F[i] += 1
        if v == -1:
            F[i+1] -= 1
ans = max(list(accumulate(F)))
print(ans)

Submission status: Accepted

Solution code:
n,c=map(int,input().split())
ls=[[set(),set()] for i in range(30)]
l=[0]*(10**5+1)
for i in range(n):
    s,t,c=map(int,input().split())
    if s in ls[c-1][1]:ls[c-1][1].remove(s)
    else:ls[c-1][0].add(s-1)
    if t-1 in ls[c-1][0]:ls[c-1][0].remove(t-1)
    else:ls[c-1][1].add(t)
for i in ls:
    for j in i[0]:
        l[j]+=1
    for j in i[1]:
        l[j]-=1
for i in range(10**5):
    l[i+1]+=l[i]
print(max(l))

Submission status: Accepted

Solution code:
# 計算量 O(NC) = O(3 * 10 ** 6)
import sys
input = sys.stdin.readline
import numpy as np

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

# 入力
lst = [[0] * (10 ** 5 + 10) for _ in range(C + 1)]
# lst_max = [[1] * (10 ** 5 + 10) for _ in range(C + 1)]

# lst = [[0] * (10) for _ in range(C + 1)]
# lst_max = [[1] * (10) for _ in range(C + 1)]

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

lst = np.array(lst)
np.cumsum(lst, axis = 1, out = lst)
np.minimum(lst, 1, out = lst)
np.cumsum(lst, axis = 0, out = lst)

print (np.max(lst[-1]))

Submission status: Accepted

Solution code:
# 計算量 O(NC) = O(3 * 10 ** 6)
import sys
input = sys.stdin.readline
import numpy as np

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

# 入力
lst = [[0] * (10 ** 5 + 10) for _ in range(C + 1)]
lst_max = [[1] * (10 ** 5 + 10) for _ in range(C + 1)]

# lst = [[0] * (10) for _ in range(C + 1)]
# lst_max = [[1] * (10) for _ in range(C + 1)]

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

lst = np.array(lst)
np.cumsum(lst, axis = 1, out = lst)
np.minimum(lst, lst_max, out = lst)
np.cumsum(lst, axis = 0, out = lst)

print (np.max(lst[-1]))

Submission status: Accepted

Solution code:
from operator import itemgetter

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

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

Q = []
for ps in P:
    ps.sort(key=itemgetter(0))
    if not ps:
        continue
    for i, (s, t) in enumerate(ps):
        if i == 0:
            pres = s
            pret = t
            continue
        if s == pret:
            pret = t
            continue
        Q.append((pres-1, pret))
        pres = s
        pret = t
    Q.append((pres-1, pret))

imos = [0 for _ in range(100003)]
for qx, qy in Q:
    imos[qx] += 1
    imos[qy] -= 1

for i in range(100002):
    imos[i] += imos[i-1]
print(max(imos))

Submission status: Accepted

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

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

STC.sort()

rec = []
for i in range(N):
    found = False
    for j in range(len(rec)):
        if (rec[j][0] < STC[i][0] and rec[j][1] != STC[i][2]) or (rec[j][0] <= STC[i][0] and rec[j][1] == STC[i][2]):
            found, rec[j] = True, (STC[i][1], STC[i][2])
            break
    if not found:
        rec.append((STC[i][1], STC[i][2]))

print(len(rec))

Submission status: Accepted

Solution code:
# 計算量 O(NC) = O(3 * 10 ** 6)
import sys
input = sys.stdin.readline

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

# 入力
lst = [[0] * (10 ** 5 + 10) for _ in range(C + 1)]

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

#番組ごとに毎分必要かどうかを判断する
for i in range(1, C + 1):
    for j in range(1, 10 ** 5 + 10): #いもす法で計算
        lst[i][j] += lst[i][j - 1]
    for j in range(1, 10 ** 5 + 10): #重なっている時 = 連続して使う時
        lst[i][j] = min(1, lst[i][j])

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

print (max(lst[-1]))

Submission status: Accepted

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

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

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