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:
# 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]*(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][s] == -1:
        tbl[c][s] = 0
        tbl[c][t] = -1
    elif tbl[c][t-1] == 1:
        tbl[c][s] = 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)

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

Submission status: Wrong Answer

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]*(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][s] == 1:
        tbl[c][s] = 0
        tbl[c][t] = -1
    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)

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

Submission status: Wrong Answer

Solution code:
n, c = [ int(v) for v in input().split() ]
time = [ 0 for i in range(10**5+2) ]
time2 = [ 0 for i in range(10**5+2) ]

channnel_list = [ [] for i in range(c) ]
for i in range(n):
	s, t, r = [ int(v) for v in input().split() ]
	channnel_list[r-1].append([r-1,s,t])


for i in range(c):
	for j in range(len(channnel_list[i])-1):
		if channnel_list[i][j+1][1] == channnel_list[i][j][2]:
			channnel_list[i][j+1][1] = channnel_list[i][j][1]
			channnel_list[i][j][0] = -1

for i in range(c):
	for j in range(len(channnel_list[i])):
		if channnel_list[i][j][0] != -1:
			time[channnel_list[i][j][1]] += 1
			time[channnel_list[i][j][2]+1] -= 1

time2[0] = time[0]
for i in range(10**5+1):
	time2[i+1] += (time2[i] + time[i+1])

print(max(time2))

Submission status: Wrong Answer

Solution code:

n, c = [ int(v) for v in input().split() ]
time = [ 0 for i in range(10**5+2) ]
time2 = [ 0 for i in range(10**5+2) ]

channnel_list = [ [] for i in range(c) ]
for i in range(n):
	s, t, r = [ int(v) for v in input().split() ]
	channnel_list[r-1].append([r-1,s,t])


for i in range(c):
	for j in range(len(channnel_list[i])-1):
		if channnel_list[i][j+1][1] == channnel_list[i][j][2]:
			channnel_list[i][j+1][1] = channnel_list[i][j][1]
			channnel_list[i][j][0] = -1

for i in range(c):
	for j in range(len(channnel_list[i])):
		if channnel_list[i][j][0] != -1:
			time[channnel_list[i][j][1]] += 1
			time[channnel_list[i][j][2]+1] -= 1

for i in range(10**5+1):
	time2[i+1] += (time2[i] + time[i+1])

print(max(time2))

Submission status: Wrong Answer

Solution code:
n, c = [ int(v) for v in input().split() ]
time = [ 0 for i in range(10**5+2) ]
time2 = [ 0 for i in range(10**5+2) ]

channnel_list = [ [] for i in range(c) ]
for i in range(n):
	s, t, r = [ int(v) for v in input().split() ]
	channnel_list[r-1].append([r-1,s,t])


for i in range(c):
	for j in range(len(channnel_list[i])-1):
		if channnel_list[i][j+1][1] == channnel_list[i][j][2]:
			channnel_list[i][j+1][1] = channnel_list[i][j][1]
			channnel_list[i][j][0] = -1

for i in range(c):
	for j in range(len(channnel_list[i])):
		if channnel_list[i][j][0] != -1:
			time[channnel_list[i][j][1]] += 1
			time[channnel_list[i][j][2]+1] -= 1

for i in range(10**5):
	time2[i+1] += (time2[i] + time[i+1])

print(max(time2))

Submission status: Wrong Answer

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 = []
    d.append([0]*N_max)
    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: Wrong Answer

Solution code:
n,C=map(int,input().split())
N=10**5+1
INF = 2**31-1
 
LV = N.bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)
 
def gindex(l, r):
    L = l + N0; R = r + N0
    lm = (L // (L & -L)) >> 1
    rm = (R // (R & -R)) >> 1
    while L < R:
        if R <= rm:
            yield R
        if L <= lm:
            yield L
        L >>= 1; R >>= 1
    while L:
        yield L
        L >>= 1
 
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0
 
def update(l, r, x):
    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; data[L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in gindex(l, r):
        data[i-1] = min(data[2*i-1], data[2*i]) + lazy[i-1]
 
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r
 
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

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

print(-query(0,N+1))

Submission status: Wrong Answer

Solution code:
n,C=map(int,input().split())
N=10**5+1
INF = 2**31-1
 
LV = N.bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)
 
def gindex(l, r):
    L = l + N0; R = r + N0
    lm = (L // (L & -L)) >> 1
    rm = (R // (R & -R)) >> 1
    while L < R:
        if R <= rm:
            yield R
        if L <= lm:
            yield L
        L >>= 1; R >>= 1
    while L:
        yield L
        L >>= 1
 
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0
 
def update(l, r, x):
    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; data[L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in gindex(l, r):
        data[i-1] = min(data[2*i-1], data[2*i]) + lazy[i-1]
 
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r
 
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

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

print(-query(0,N))

Submission status: Wrong Answer

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

input=sys.stdin.readline
n,C=map(int,input().split())
N=10**5+1
INF = 2**31-1
 
LV = N.bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)
 
def gindex(l, r):
    L = l + N0; R = r + N0
    lm = (L // (L & -L)) >> 1
    rm = (R // (R & -R)) >> 1
    while L < R:
        if R <= rm:
            yield R
        if L <= lm:
            yield L
        L >>= 1; R >>= 1
    while L:
        yield L
        L >>= 1
 
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0
 
def update(l, r, x):
    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; data[L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in gindex(l, r):
        data[i-1] = min(data[2*i-1], data[2*i]) + lazy[i-1]
 
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r
 
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for i in range(n):
    s,t,c=map(int,input().split())
    s-=1
    update(s,t,-1)
    
print(-query(0,N))

Submission status: Wrong Answer

Solution code:
N, C = map(int, input().split())
num = 10**5+1
count = [0]*(num)
channel = [0]*num
for i in range(N):
    s, t, c = map(int, input().split())
    if channel[s]==c and channel[t-1]==c:
        count[s]+=1
        count[t-1]-=1
    elif channel[s]==c:#はじめ＝終わり
        count[s]+=1
        count[t]-=1
    elif channel[t-1]==c:
        count[t-1]-=1
        count[s-1]+=1
    else:
        count[s-1]+=1
        count[t]-=1
    channel[s-1]=c
    channel[t]=c
for i in range(1, num):
    count[i]+=count[i-1]
print(max(count))

Submission status: Wrong Answer

Solution code:
N, C = map(int, input().split())
num = 10**5+1
count = [0]*(num)
channel = [0]*num
for i in range(N):
    s, t, c = map(int, input().split())
    print(count)
    if channel[s]==c and channel[t-1]==c:
        count[s]+=1
        count[t-1]-=1
    elif channel[s]==c:#はじめ＝終わり
        count[s]+=1
        count[t]-=1
    elif channel[t-1]==c:
        count[t-1]-=1
        count[s-1]+=1
    else:
        count[s-1]+=1
        count[t]-=1
    channel[s-1]=c
    channel[t]=c
print(count)
for i in range(1, num):
    count[i]+=count[i-1]
print(max(count))

Submission status: Wrong Answer

Solution code:
N, C = map(int, input().split())
num = 10**5+1
count = [0]*(num)
channel = [0]*num
for i in range(N):
    s, t, c = map(int, input().split())
    if channel[s]==c:#はじめ＝終わり
        count[s]-=1
        count[t]+=1
        if channel[t-1]==c:
            count[t-1]-=1
            count[s-1]+=1
    elif channel[t-1]==c:
        count[t-1]-=1
        count[s-1]+=1
    else:
        count[s-1]+=1
        count[t]-=1
    channel[s-1]=c
    channel[t]=c
for i in range(1, num):
    count[i]+=count[i-1]
print(max(count))

Submission status: Wrong Answer

Solution code:
N, C = map(int, input().split())
num = 10**5+1
count = [0]*(num)
channel = [0]*num
for i in range(N):
    s, t, c = map(int, input().split())
    if channel[s]==c:#はじめ＝終わり
        count[s]-=1
        count[t]+=1
    elif channel[t-1]==c:
        count[t-1]-=1
        count[s-1]+=1
    else:
        count[s-1]+=1
        count[t]-=1
    channel[s-1]=c
    channel[t]=c
for i in range(1, num):
    count[i]+=count[i-1]
print(max(count))

Submission status: Wrong Answer

Solution code:
N, C = map(int, input().split())
num = 10**5+1
count = [0]*(num)
channel = [0]*num
for i in range(N):
    s, t, c = map(int, input().split())
    if channel[s]==c:#はじめ＝終わり
        count[s]-=0
        count[t]+=1
    elif channel[t-1]==c:
        count[t-1]-=1
        count[s-1]+=1
    else:
        count[s-1]+=1
        count[t]-=1
    channel[s-1]=c
    channel[t]=c
for i in range(1, num):
    count[i]+=count[i-1]
print(max(count))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import heapq

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

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

heap = []
res = 0


for i in range(1, 10001):
    nex = set([])
    rem = set([])
    while heap and heap[0][0] == i:
        t1,c1 = heapq.heappop(heap)
        rem.add((t1,c1))

    while inl and inl[-1][0] == i:
        s,t,c = inl.pop()
        nex.add((s,c))
        heapq.heappush(heap, (t,c))
    res = max(res, len(heap) + len(rem) - len(rem.intersection(nex)))

print(res)

Submission status: Wrong Answer

Solution code:
import heapq

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

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

heap = []
res = 0


for i in range(1, 10001):
    nex = set([])
    rem = set([])

    con = 0
    while heap and heap[0][0] == i:
        t1,c1 = heapq.heappop(heap)
        rem.add((t1,c1))

    while inl and inl[-1][0] == i:
        s,t,c = inl.pop()
        nex.add((s,c))
        heapq.heappush(heap, (t,c))

    con = len(heap) + len(rem) - len(rem.intersection(nex))
    res = max(res, con)

print(res)

Submission status: Wrong Answer

Solution code:
import heapq

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

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

heap = []
res = 0


for i in range(1, 10001):
    rem = set([])
    add = 0
    while heap and heap[0][0] == i:
        t1,c1 = heapq.heappop(heap)
        rem.add((t1,c1))

    while inl and inl[-1][0] == i:
        s,t,c = inl.pop()
        heapq.heappush(heap, (t,c))
        if not (s,c) in rem:
            add += 1

    res = max(res, len(heap) + min(add, len(rem)))

print(res)

Submission status: Wrong Answer

Solution code:
import heapq

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

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

heap = []

res = 0


for i in range(1, 10001):
    nex = set([])
    rem = set([])

    con = 0
    while inl and inl[-1][0] == i:
        s,t,c = inl.pop()
        nex.add((s,c))
        heapq.heappush(heap, (t,c))

    while heap and heap[0][0] == i:
        t1,c1 = heapq.heappop(heap)
        rem.add((t1,c1))

    con = len(heap) + min(len(nex), len(rem))
    res = max(res, con)

print(res)

Submission status: Wrong Answer

Solution code:
import heapq

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

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

heap = []

res = 0


for i in range(1, 10001):
    nex = set([])
    rem = set([])

    con = 0
    while inl and inl[-1][0] == i:
        s,t,c = inl.pop()
        nex.add((s,c))
        heapq.heappush(heap, (t,c))

    while heap and heap[0][0] == i:
        t1,c1 = heapq.heappop(heap)
        rem.add((t1,c1))

    con = len(heap) + min(len(nex) - len(rem.intersection(nex)), len(rem) - len(rem.intersection(nex)))
    res = max(res, con)

print(res)

Submission status: Wrong Answer

Solution code:
import heapq

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

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

heap = []

res = 0


for i in range(1, 10001):
    nex = set([])
    rem = set([])

    con = 0
    while inl and inl[-1][0] == i:
        s,t,c = inl.pop()
        nex.add((s,c))
        heapq.heappush(heap, (t,c))

    while heap and heap[0][0] == i:
        t1,c1 = heapq.heappop(heap)
        rem.add((t1,c1))

    con = len(heap) + min(len(nex), len(rem)-len(rem.intersection(nex)))
    res = max(res, con)

print(res)

Submission status: Wrong Answer

Solution code:
import heapq

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

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

heap = []

res = 0


for i in range(1, 10001):
    nex = set([])
    rem = set([])

    con = 0
    while inl and inl[-1][0] == i:
        s,t,c = inl.pop()
        nex.add((s,c))
        heapq.heappush(heap, (t,c))

    while heap and heap[0][0] == i:
        t1,c1 = heapq.heappop(heap)
        rem.add((t1,c1))

    con = len(heap) + len(rem)# - len(rem.intersection(nex))
    res = max(res, con)

print(res)

Submission status: Wrong Answer

Solution code:
import heapq

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

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

heap = []

res = 0

# for s,t,c in inl:
#     con = 0
#     while heap:
#         t1, c1 = heapq.heappop(heap)
#         if t1 <= s:
#             if t1 == s:
#                 con = 1
#         else:
#             heapq.heappush(heap, (t1,c1))
#             break
#     heapq.heappush(heap,(t,c))
#     con += len(heap)
#     res = max(res, con)

for i in range(1, 10001):
    nex = set([])
    rem = set([])

    con = 0
    while inl and inl[-1][0] == i:
        s,t,c = inl.pop()
        nex.add((s,c))
        heapq.heappush(heap, (t,c))

    while heap and heap[0][0] == i:
        t1,c1 = heapq.heappop(heap)
        rem.add((t1,c1))

    con = len(heap) + len(rem) - len(rem.intersection(nex))
    res = max(res, con)

print(res)

Submission status: Wrong Answer

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

for s,t,c in inl:
    con = 0
    while heap:
        t1, c1 = heapq.heappop(heap)
        if t1 <= s:
            if t1 == s:
                con = 1
        else:
            heapq.heappush(heap, (t1,c1))
            break
    heapq.heappush(heap,(t,c))
    con += len(heap)
    res = max(res, con)

print(res)

Submission status: Wrong Answer

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

for s,t,c in inl:
    con = 0
    while heap:
        t1, c1 = heapq.heappop(heap)
        if t1 <= s:
            if t1 == s and c1 != c:
                con = 1
        else:
            heapq.heappush(heap, (t1,c1))
            break
    heapq.heappush(heap,(t,c))
    con += len(heap)
    res = max(res, con)

print(res)

Submission status: Wrong Answer

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

for s,t,c in inl:
    con = 0
    while heap:
        t1, c1 = heapq.heappop(heap)
        if t1 <= s:
            if t1 == s and c1 != c:
                con += 1
        else:
            heapq.heappush(heap, (t1,c1))
            break
    heapq.heappush(heap,(t,c))
    con += len(heap)
    res = max(res, con)

print(res)

Submission status: Wrong Answer

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

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


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

print(ans)

Submission status: Wrong Answer

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

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

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

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

P2 = []

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

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

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

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

print(max_count)