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: Wrong Answer

Solution code:
class Segment_Tree_with_Lazy:
    def __init__(self,N):  # N: 処理する区間の長さ
        self.ID = 0
        self.LV = (N-1).bit_length()
        self.N0 = 2**self.LV
        self.data = [self.ID]*(2*self.N0)
        self.lazy = [0]*(2*self.N0)

    #  伝搬対象の区間を求める
    def gindex(self,l,r):
        L = (l + self.N0) >> 1
        R = (r + self.N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(self.LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1
            R >>= 1

    #  遅延伝搬処理
    def propagetes(self,*ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if not v:continue
            self.lazy[2 * i - 1] = self.data[2 * i - 1] = v
            self.lazy[2 * i] = self.data[2 * i] = v
            self.lazy[i-1] = 0

    #  区間[l, r)にx加算
    def update(self,l,r,x):
        *ids, = Segment_Tree_with_Lazy.gindex(self, l, r)
        Segment_Tree_with_Lazy.propagetes(self, *ids)

        L = self.N0 + l
        R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] += x
                self.data[R-1] += x
            if L & 1:
                self.lazy[L-1] += x
                self.data[L-1] += x
                L += 1
            L >>= 1
            R >>= 1
        for i in ids:
            self.data[i-1] = max(self.data[2*i-1], self.data[2*i])

    #  区間[l, r)内の最大値を求める
    def query(self, l, r):
        *ids, = Segment_Tree_with_Lazy.gindex(self, l, r)
        Segment_Tree_with_Lazy.propagetes(self, *ids)

        L = self.N0 + l
        R = self.N0 + r

        s = self.ID
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1

        return s

n,c = map(int, input().split())
seg = Segment_Tree_with_Lazy(2*10**5 + 2)

for _ in range(n):
    s,t,c = map(int, input().split())
    seg.update(2*s-1,2*t+1,1)

print(seg.query(0,2*10**5+2))

Submission status: Wrong Answer

Solution code:
class Segment_Tree_with_Lazy:
    def __init__(self,N):  # N: 処理する区間の長さ
        self.ID = 0
        self.LV = (N-1).bit_length()
        self.N0 = 2**self.LV
        self.data = [self.ID]*(2*self.N0)
        self.lazy = [0]*(2*self.N0)

    #  伝搬対象の区間を求める
    def gindex(self,l,r):
        L = (l + self.N0) >> 1
        R = (r + self.N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(self.LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1
            R >>= 1

    #  遅延伝搬処理
    def propagetes(self,*ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if not v:continue
            self.lazy[2 * i - 1] = self.data[2 * i - 1] = v
            self.lazy[2 * i] = self.data[2 * i] = v
            self.lazy[i-1] = 0

    #  区間[l, r)にx加算
    def update(self,l,r,x):
        *ids, = Segment_Tree_with_Lazy.gindex(self, l, r)
        Segment_Tree_with_Lazy.propagetes(self, *ids)

        L = self.N0 + l
        R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] += x
                self.data[R-1] += x
            if L & 1:
                self.lazy[L-1] += x
                self.data[L-1] += x
                L += 1
            L >>= 1
            R >>= 1
        for i in ids:
            self.data[i-1] = max(self.data[2*i-1], self.data[2*i])

    #  区間[l, r)内の最大値を求める
    def query(self, l, r):
        *ids, = Segment_Tree_with_Lazy.gindex(self, l, r)
        Segment_Tree_with_Lazy.propagetes(self, *ids)

        L = self.N0 + l
        R = self.N0 + r

        s = self.ID
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1

        return s

n,c = map(int, input().split())
seg = Segment_Tree_with_Lazy(2*10**5 + 2)

for _ in range(n):
    s,t,c = map(int, input().split())
    seg.update(2*s-1,2*t,1)

print(seg.query(0,2*10**5+1))

Submission status: Wrong Answer

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

ans = 0

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

time = 10**5+3

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

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

#print(c_imos)

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

for i in range(c):
    for j in range(time):
        if j == 0:
            if c_imos[i][j] == 1:
                nd_v[i][j] = 1
        else:
            nd_v[i][j] = max(0,min(1,nd_v[i][j-1] + c_imos[i][j]))
#print(nd_v)

ans = 1

for i in range(time-1):
    tmp = 0
    for j in range(c):
        tmp += nd_v[j][i]
    ans = max(tmp,ans)

print(ans)

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

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

ans = 1
ans_tmp = 1

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

Submission status: Wrong Answer

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

ans = 0

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

time = 10**5+1

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

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

#print(c_imos)

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

for i in range(c):
    for j in range(time):
        if j == 0:
            if c_imos[i][j] == 1:
                nd_v[i][j] = 1
        else:
            nd_v[i][j] = max(0,min(1,nd_v[i][j-1] + c_imos[i][j]))
#print(nd_v)

ans = 1

for i in range(time-1):
    tmp = 0
    for j in range(c):
        tmp += nd_v[j][i]
    ans = max(tmp,ans)

print(ans)

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

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

ans = 1
ans_tmp = 1

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

Submission status: Wrong Answer

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

ans = 0

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

time = 10**5+1

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

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

#print(c_imos)

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

for i in range(c):
    for j in range(time):
        if j == 0:
            if c_imos[i][j] == 1:
                nd_v[i][j] = 1
        else:
            nd_v[i][j] = min(1,nd_v[i][j-1] + c_imos[i][j])
#print(nd_v)

ans = 1

for i in range(time-1):
    tmp = 0
    for j in range(c):
        tmp += nd_v[j][i]
    ans = max(tmp,ans)

print(ans)

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

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

ans = 1
ans_tmp = 1

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

Submission status: Wrong Answer

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

ans = 0

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

time = 10**5+1

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

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

#print(c_imos)

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

for i in range(c):
    for j in range(time-1):
        if j == 0:
            if c_imos[i][j] == 1:
                nd_v[i][j] = 1
        else:
            nd_v[i][j] = min(1,nd_v[i][j-1] + c_imos[i][j])
#print(nd_v)

ans = 1

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

print(ans)

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

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

ans = 1
ans_tmp = 1

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

Submission status: Wrong Answer

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

ans = 0

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

time = 10**5+1

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

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

#print(c_imos)

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

for i in range(c):
    for j in range(time):
        if j == 0:
            if c_imos[i][j] == 1:
                nd_v[i][j] = 1
        else:
            nd_v[i][j] = max(0,min(1,nd_v[i][j-1] + c_imos[i][j]))
#print(nd_v)

ans = 1

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

print(ans)

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

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

ans = 1
ans_tmp = 1

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

Submission status: Wrong Answer

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

ans = 0

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

time = 10**5+1

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

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

#print(c_imos)

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

for i in range(c):
    for j in range(time):
        if j == 0:
            if c_imos[i][j] == 1:
                nd_v[i][j] = 1
        else:
            nd_v[i][j] = min(1,nd_v[i][j-1] + c_imos[i][j])
#print(nd_v)

ans = 1

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

print(ans)

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

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

ans = 1
ans_tmp = 1

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

Submission status: Wrong Answer

Solution code:


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

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

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

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

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

    print(curr_max)


submit()

Submission status: Wrong Answer

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

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

ans=0
for i in range(c):
    if lst[i]!=0:
        ans+=1
print(ans)

Submission status: Wrong Answer

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

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

ans=0
for i in range(c):
    if lst[i]!=0:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

def main():
    N, C = map(int, input().split())
    STC = [tuple(map(int, input().split())) for _ in range(N)]
    STC.sort()
    h = []
    e = []
    r = 0
    for s, t, c in STC:
        while h and h[0][0] <= s:
            e.append(heapq.heappop(h)[1])
        if not e:
            e.append(r)
            r += 1
        heapq.heappush(h, (t, e.pop()))
    return r

print(main())

Submission status: Wrong Answer

Solution code:
import heapq

def main():
    N, C = map(int, input().split())
    STC = [tuple(map(int, input().split())) for _ in range(N)]
    STC.sort()
    h = []
    e = []
    r = 0
    for s, t, c in STC:
        while h and h[0][0] <= s:
            e.append(heapq.heappop(h)[1])
        if not e:
            e.append(r)
            r += 1
        heapq.heappush(h, (t + 1, e.pop()))
    return r

print(main())

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

ans = 0
v = 0
for i in range(10**5+1):
    for c in range(C):
        v += imos[c][i]
    ans = max(ans, v)
print(ans)

Submission status: Wrong Answer

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

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

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

for _ in range(n):
    s, t, c = map(int, input().split())
    imos[(s*2) - 1] += 1
    imos[t*2 + 1] -= 1

ans = 0
v = 0
for i in range(len(imos)):
    v += imos[i]
    imos[i] = v
    ans = max(ans, v)

print(ans)

Submission status: Wrong Answer

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

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

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

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

ans = 0
v = 0
for i in range(len(imos)):
    v += imos[i]
    imos[i] = v
    ans = max(ans, v)

print(ans)

Submission status: Wrong Answer

Solution code:
n,c=map(int,input().split())
stc=[[i for i in map(int,input().split())] for _ in range(n)]
stc.sort(key=lambda x:x[1])
check=[0]*n
ans=0
for i in range(1,c+1):
  prechannel=-1
  pretime=-1
  for j in range(n):
    if check[j]:
      continue
    s,t,c=stc[j]
    if c!=prechannel:
      if s>pretime:
        pretime=t
        prechannel=c
        ans+=1
        check[j]=1
    else:
      if s>=pretime:
        pretime=t
        prechannel=c
        ans+=1
        check[j]=1
  if ans==n:
    print(i)
    break

Submission status: Wrong Answer

Solution code:
n,c=map(int,input().split())
stc=[[i for i in map(int,input().split())] for _ in range(n)]
stc.sort(key=lambda x:x[1])
check=[0]*n
ans=0
for i in range(1,c+1):
  prechannel=-1
  pretime=-1
  for j in range(n):
    if stc[j]:
      continue
    s,t,c=stc[j]
    if c!=prechannel:
      if s>pretime:
        pretime=t
        prechannel=c
        ans+=1
        check[j]=1
    else:
      if s>=pretime:
        pretime=t
        prechannel=c
        ans+=1
        check[j]=1
  if ans==n:
    print(i)
    break

Submission status: Wrong Answer

Solution code:
N,C = map(int,input().split())
T = [[0 for i in range(C)] for j in range(10**5+1)]

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

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

Submission status: Wrong Answer

Solution code:
N,C = map(int,input().split())
T = [0 for i in range(10**5+1)]

for i in range(N):
    s,t,c = map(int,input().split())
    T[s] += 1
    if t < 10**5:
        T[t+1] -= 1
for i in range(10**5):
    T[i+1] += T[i]
print(max(T))

Submission status: Wrong Answer

Solution code:
N,C = map(int,input().split())
T = [0 for i in range(10**5+1)]

for i in range(N):
    s,t,c = map(int,input().split())
    T[s] += 1
    T[min(t+1,10**5)] -= 1
for i in range(10**5):
    T[i+1] += T[i]
print(max(T))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

    n,c = map(int, input().split())
    tv = [[] for _ in range(c)]
    for _ in range(n):
        s,t,ch = map(int, input().split())
        tv[ch-1].append([s,t])
    ntv = []
    for i in range(c):
        tv[i].sort()
        x = 0
        while x < (len(tv[i])-1):
            if tv[i][x][1] == tv[i][x+1][0]:
                s,t = tv[i].pop(x)
                tv[i][x][0] = s
            else:
                x += 1
    for i in tv:
        for s,t in i:
            ntv.append([s,t,0])

    ntv.sort(key=lambda a: a[1])

    res = 0
    for _ in range(c):
        cur = 0
        for i in range(len(ntv)):
            if ntv[i][2]:
                continue
            if cur <= (ntv[i][0]-0.5):
                cur = ntv[i][1]
                ntv[i][2] = 1
        if cur:
            res += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

    n,c = map(int, input().split())
    tv = [[] for _ in range(c)]
    for _ in range(n):
        s,t,ch = map(int, input().split())
        tv[ch-1].append([s,t])
    ntv = []
    for i in range(c):
        tv[i].sort()
        x = 0
        while x < (len(tv[i])-1):
            if tv[i][x][1] == tv[i][x+1][0]:
                s,t = tv[i].pop(x)
                tv[i][x][0] = s
            else:
                x += 1
    for i in tv:
        for s,t in i:
            ntv.append([s,t,0])

    ntv.sort(key=lambda a: a[1])

    res = 0
    for _ in range(30):
        cur = 0
        for i in range(len(ntv)):
            if ntv[i][2]:
                continue
            if cur <= (ntv[i][0]-0.5):
                cur = ntv[i][1]
                ntv[i][2] = 1
        if cur:
            res += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools

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

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

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

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

Submission status: Wrong Answer

Solution code:
import itertools

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

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

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

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

Submission status: Wrong Answer

Solution code:
import itertools

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

for c, x in itertools.product(range(C), range(10 ** 5)):
    if table[c][x] == 1 and table[c][x + 1] == -1:
        table[c][x], table[c][x + 1] = 0, 0

for c in range(C):
    table[c] = tuple(itertools.accumulate(table[c]))
print(max(sum(table[c][x] for c in range(C)) for x in range(10 ** 5 + 1)))

Submission status: Wrong Answer

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

# なぜか2WAが取れない

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

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

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

# 1 3
# 3 4 2

Submission status: Wrong Answer

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

ans=1
for j in range(0,10**5):
    su=0
#    print(c,'hello')
    for i in range(c):
#        print('asdf hello')
#        print(j,i,a[i][j])
        su+=a[i][j]
    ans=max(ans,su)
print(ans)

Submission status: Wrong Answer

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

ans=1
for j in range(0,10**5):
    su=0
#    print(c,'hello')
    for i in range(c):
#        print('asdf hello')
#        print(j,i,a[i][j])
        su+=a[i][j]
    ans=max(ans,su)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np
n, c = map(int,input().split())
stc = [list(map(int, input().split())) for _ in range(n)]

result = np.zeros(2*10**5)
for s, t, c in stc:
    result[2*s-1:2*t-1] += 1
print(int(max(result)))

Submission status: Wrong Answer

Solution code:
import numpy as np
n, c = map(int,input().split())
stc = [list(map(int, input().split())) for _ in range(n)]

result = np.zeros(2*10**5)
for s, t, c in stc:
    result[2*s-1:2*t] += 1
print(int(max(result)))