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: Time Limit Exceeded

Solution code:

if __name__ == '__main__':
    N,C=list(map(int,input().split()))
    recording={i:[] for i in range(C)}
    end=0
    for i in range(N):
        s,t,c=list(map(int,input().split()))
        recording[c-1].append((s,t))
        end=max(end,t)

    imos=[[0 for i in range((end+1)*10)] for j in range(C)]
    for c in range(C):
        for s,t in recording[c]:
            s*=10
            t*=10
            if imos[c][s]!=-1:
                imos[c][s-5]=1
                imos[c][t]=-1
            elif imos[c][s]==-1:
                imos[c][s]=0
                imos[c][t]=-1

    for c in range(C):
        for i in range(1,(end+1)*10):
            if imos[c][i-1]==1 and imos[c][i]!=-1:
                imos[c][i]=1

    count=0

    for i in range(1,(end+1)*10):
        temp=0
        for c in range(C):
            if imos[c][i]==1:
                temp+=1
        count=max(count,temp)

    print(count)

Submission status: Time Limit Exceeded

Solution code:


if __name__ == '__main__':
    N,C=list(map(int,input().split()))
    recording={i:[] for i in range(C)}
    end=0
    for i in range(N):
        s,t,c=list(map(int,input().split()))
        recording[c-1].append((s-0.5,t))
        end=max(end,t)

    count=0

    for i in range(0,end*10,5):
        i=i/10
        overlap=0
        for channel in recording.values():
            for on_air in channel:
                if on_air[0]<=i<on_air[1]:
                    overlap+=1
        count=max(count,overlap)

    print(count)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7

input = sys.stdin.readline
def main():
    n, c = map(int, input().split())
    stk = [tuple(map(int, input().split())) for i in range(n)]
    stk = sorted(stk, key=lambda x: x[0])

    ans = 1
    l = []
    heapify(l)
    heappush(l, (stk[0][1], stk[0][2]))
    for i in range(1, n):
        ll = []
        heapify(ll)
        size = len(l)
        for j in range(size):
            v = heappop(l)
            if stk[i][2] == v[1]:
                if stk[i][0] < v[0]:
                    heappush(ll, v)
            else:
                if stk[i][0] - 0.5 < v[0]:
                    heappush(ll, v)
        heappush(ll, stk[i][1:])
        l = ll
        ans = max(ans, len(l))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7

input = sys.stdin.readline
def main():
    n, c = map(int, input().split())
    stk = [list(map(int, input().split())) for i in range(n)]
    stk = sorted(stk, key=lambda x: x[0])

    ans = 1
    l = []
    heapify(l)
    heappush(l, [stk[0][1], stk[0][2]])
    for i in range(1, n):
        ll = []
        heapify(ll)
        size = len(l)
        for j in range(size):
            v = heappop(l)
            if stk[i][2] == v[1]:
                if stk[i][0] < v[0]:
                    heappush(ll, v)
            else:
                if stk[i][0] - 0.5 < v[0]:
                    heappush(ll, v)
        heappush(ll, stk[i][1:])
        l = ll
        ans = max(ans, len(l))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
 
def main():
    n, c = map(int, input().split())
    stk = [list(map(int, input().split())) for i in range(n)]
    stk = sorted(stk,key=lambda x:x[0])
 
    ans = 1
    l = []
    heapify(l)
    heappush(l,[stk[0][1],stk[0][2]])
    for i in range(1, n):
        ll = []
        heapify(ll)
        size = len(l)
        for j in range(size):
            v = heappop(l)
            if stk[i][2] == v[1]:
                if stk[i][0] < v[0]:
                    heappush(ll,v)
            else:
                if stk[i][0] - 0.5 < v[0] :
                    heappush(ll,v)
        heappush(ll, stk[i][1:])
        l = ll
        ans = max(ans , len(l))
    print(ans)
 
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import numpy as np
N,C=map(int,input().split())
X=np.array([[0]*(2*10**5+2)]*(C+1))
for i in range(N):
  s,t,c=map(int,input().split())
  s=2*s-1
  t=2*t
  for j in range(s,t+1):
    X[c][j]=1
answer=max(X.sum(axis=0))
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
N,C=map(int,input().split())
X=np.array([[0]*(2*10**5+10)]*C)
for i in range(N):
  s,t,c=map(int,input().split())
  s=2*s-1
  t=2*t
  for j in range(s,t+1):
    X[c-1][j]=1
answer=max(X.sum(axis=0))
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import numpy as np
N,C=map(int,input().split())
X=np.array([[0]*(2*10**5+10)]*(C+1))
for i in range(N):
  s,t,c=map(int,input().split())
  s=2*s-1
  t=2*t
  for j in range(s,t+1):
    X[c][j]=1
answer=max(X.sum(axis=0))
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7

def main():
    n, c = map(int, input().split())
    stk = [list(map(int, input().split())) for i in range(n)]
    stk = sorted(stk,key=lambda x:x[0])

    ans = 1
    l = []
    heapify(l)
    heappush(l,[stk[0][1],stk[0][2]])
    for i in range(1, n):
        ll = []
        heapify(ll)
        size = len(l)
        for j in range(size):
            v = heappop(l)
            if stk[i][2] == v[1]:
                if stk[i][0] < v[0]:
                    heappush(ll,v)
            else:
                if stk[i][0] - 0.5 < v[0] :
                    heappush(ll,v)
        heappush(ll, stk[i][1:])
        l = ll
        ans = max(ans , len(l))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7

def main():
    n, c = map(int, input().split())
    stk = [list(map(int, input().split())) for i in range(n)]
    stk = sorted(stk,key=lambda x:x[0])

    ans = 1
    l = []
    heapify(l)
    heappush(l,[stk[0][1],stk[0][2]])
    for i in range(1, n):
        ll = []
        size = len(l)
        for j in range(size):
            v = heappop(l)
            if stk[i][2] == v[1]:
                if stk[i][0] < v[0]:
                    ll.append(v)
            else:
                if stk[i][0] - 0.5 < v[0] :
                    ll.append(v)
        for j in range(len(ll)):
            heappush(l, ll[j])
        
        heappush(l, stk[i][1:])
        ans = max(ans , len(l))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ans = [[0, 0] for _ in range(C)]
L.sort()
for i in range(N):
    j = 0
    while j < C:
        if ans[j][0] == L[i][0] and ans[j][1] == L[i][2]:
            ans[j][0] = L[i][1]
            j = C
        elif ans[j][0] < L[i][0]:
            ans[j][0] = L[i][1]
            ans[j][1] = L[i][2]
            j = C
        j += 1
    ans.sort(reverse=True)
    
num = 0
for i in range(C):
    if ans[i][0] > 0:
        num += 1
        
print(num)

Submission status: Time Limit Exceeded

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

rs = [[STC[0][1],STC[0][2]]]
for i in range(1,N):
  len_rs = len(rs)
  
  min_idx = None
  for j in range(len_rs):
    if rs[j][1] != STC[i][2]: tmp_stc_r = STC[i][0] - 0.5
    else: tmp_stc_r = STC[i][0]
 
    if rs[j][0] <= tmp_stc_r:
      if min_idx is None: min_idx = j
      else:
        if rs[j][0] < rs[min_idx][0]: min_idx = j

  if min_idx is None: rs.append([STC[i][1], STC[i][2]])
  else: rs[min_idx] = [STC[i][1], STC[i][2]]
  
print(len(rs))

Submission status: Time Limit Exceeded

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

rs = [[STC[0][1],STC[0][2]]]
for i in range(1,N):
  len_rs = len(rs)
  
  min_idx = None
  for j in range(len_rs):
    if rs[j][1] != STC[i][2]: tmp_stc_r = STC[i][0] - 0.5
    else: tmp_stc_r = STC[i][0]
 
    if rs[j][0] <= tmp_stc_r:
      if min_idx is None: min_idx = j
      else:
        if rs[j][0] < rs[min_idx][0]: min_idx = j

  if min_idx is None: rs.append([STC[i][1], STC[i][2]])
  else: rs[min_idx] = [STC[i][1], STC[i][2]]
  
  rs.sort()
print(len(rs))

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,c = map(int, input().split())
channels = {i:[] for i in range(1,c+1)}
table = [0 for _ in range(200004)]
for _ in range(n):
    s,t,c = map(int, input().split())
    channels[c].append([s,t])

for ch, time in channels.items():
    sub = [0 for _ in range(200004)]
    for s,t in time:
        if sub[s*2]:
            sub[s*2] = 0
        else:
            sub[s*2-1] = 1
        if sub[t*2-1]:
            sub[t*2-1] = 0
        else:
            sub[t*2] = -1
    for i in range(1,200002):
        sub[i] += sub[i-1]
        table[i] += max(0, sub[i])
ans = 0
for i in range(1,200002):
    ans = max(ans, table[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,c = map(int, input().split())
channels = [{} for _ in range((10**5+1)*2)]
ans = 0
for _ in range(n):
    s,t,c = map(int, input().split())
    s,t = s*2-1, t*2
    for i in range(s,t+1):
        if c not in channels[i]:
            channels[i][c] = 1
        ans = max(ans, len(channels[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, C = map(int,input().split())
T = [[] for _ in range(C+1)]
for _ in range(N):
    s,t,c = map(int,input().split())
    T[c].append([s,t])
for i in range(len(T)):
    times = T[i]
    times.sort()
    idx = 0
    while len(times) > 1:
        if times[idx][1] == times[idx+1][0]:
            times[idx] = [times[idx][0], times[idx+1][1]]
            del times[idx+1]
            T[i] = times
        else:
            idx += 1
        if idx == len(times)-1:
            break

import numpy as np

A = np.zeros(10**5+10,dtype=np.int32)
for u in T:
    if len(u) == 0:
        continue
    else:
        for times in u:
            A[times[0]-1] += 1
            A[times[1]] -= 1
print(max(np.cumsum(A)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, C = map(int,input().split())
T = [[] for i in range(31)]
for i in range(N):
    s,t,c = map(int,input().split())
    T[c].append([s,t])
for i in range(len(T)):
    times = T[i]
    times.sort()
    idx = 0
    while len(times) > 1:
        if times[idx][1] == times[idx+1][0]:
            times[idx] = [times[idx][0], times[idx+1][1]]
            del times[idx+1]
            T[i] = times
        else:
            idx += 1
        if idx == len(times)-1:
            break
A = np.zeros(10**5+10,dtype=np.int32)
for u in T:
    if len(u) == 0:
        continue
    else:
        for times in u:
            A[times[0]-1] += 1
            A[times[1]] -= 1
print(max(np.cumsum(A)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, C = map(int,input().split())
T = [[] for i in range(31)]
for i in range(N):
    s,t,c = map(int,input().split())
    T[c].append([s,t])
for i in range(len(T)):
    times = T[i]
    times.sort()
    idx = 0
    while len(times) > 1:
        if times[idx][1] == times[idx+1][0]:
            times[idx] = [times[idx][0], times[idx+1][1]]
            del times[idx+1]
            T[i] = times
        else:
            idx += 1
        if idx == len(times)-1:
            break
A = [0] * (10**5 + 1)
for u in T:
    if len(u) == 0:
        continue
    else:
        for times in u:
            A[times[0]-1] += 1
            A[times[1]] -= 1
print(max(np.cumsum(A)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, C = map(int,input().split())
stc = [list(map(int,input().split())) for i in range(N)]
T = [[] for i in range(31)]
for s,t,c in stc:
    T[c].append([s,t])
for i in range(len(T)):
    times = T[i]
    times.sort()
    idx = 0
    while len(times) > 1:
        if times[idx][1] == times[idx+1][0]:
            times[idx] = [times[idx][0], times[idx+1][1]]
            del times[idx+1]
            T[i] = times
        else:
            idx += 1
        if idx == len(times)-1:
            break
A = [0] * (10**5 + 1)
for u in T:
    if len(u) == 0:
        continue
    else:
        for times in u:
            A[times[0]-1] += 1
            A[times[1]] -= 1
print(max(np.cumsum(A)))

Submission status: Time Limit Exceeded

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]))

import numpy as np
lst = np.array(lst)
lst = np.cumsum(lst, axis = 0)

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

Submission status: Time Limit Exceeded

Solution code:
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: Time Limit Exceeded

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

# 入力
lst = [[0] * (10 ** 5 + 10) for _ in range(C + 1)]
# lst = [[0] * (20) 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

# # 累積和の計算
# import numpy as np
# A = np.array(lst)
# print (A)
# np.cumsum(A, axis = 1, out = A)
# print (A)
# np.cumsum(A, axis = 0)

# print (np.max(A[-1:]))
# print (A)

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

# for i in lst:
#     print (i[:20])

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

print (max(lst[-1]))
    
# for i in lst:
#     print (i[:20])

Submission status: Time Limit Exceeded

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

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

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

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

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

ans = 0
for i in range(maxT) :
    ans = max(ans, tvSum[i])

print(ans)

Submission status: Time Limit Exceeded

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

a=[[0 for i in range(N)]for i in range(C)]

for i in range(n):
    s,t,c=map(int,input().split())
    recs,rect=a[c-1][s],a[c-1][t]
    if recs==0 and rect==0:
        update(s-1,t,-1)
    elif recs==0 and rect==1:
        update(s-1,t-1,-1)
    elif recs==1 and rect==0:
        update(s,t,-1)
    elif recs==1 and rect==1 and s<t-1:
        update(s,t-1,-1)
    a[c-1][s],a[c-1][t]=1,1
print(-query(0,N+1))

Submission status: Time Limit Exceeded

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

a=[[0 for i in range(N)]for i in range(C)]

for i in range(n):
    s,t,c=map(int,input().split())
    recs,rect=a[c-1][s],a[c-1][t]
    if recs==0 and rect==0: update(s-1,t,-1)
    elif recs==0 and rect==1: update(s-1,t-1,-1)
    elif recs==1 and rect==0: update(s,t,-1)
    elif recs==1 and rect==1 and s<t-1: update(s,t-1,-1)
    a[c-1][s],a[c-1][t]=1,1
print(-query(0,N+1))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n, c = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]
x.sort(key=lambda x: [x[-1], x[0]])
ans = defaultdict(int)
cc = -1
for i in range(n):
    si, ti, ci = x[i]
    if ci != cc:
        tt = defaultdict(int)
    for j in range(2 * si - 1, 2 * ti):
        if tt[j] == 0:
            tt[j] = 1
            ans[j] += 1
    cc = ci
print(max(ans.values()))

Submission status: Time Limit Exceeded

Solution code:
n, c = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]
x.sort(key=lambda x: [x[-1], x[0]])
ans = [0 for _ in range(2 * 10 ** 5 + 2)]
cc = -1
for i in range(n):
    si, ti, ci = x[i]
    if ci != cc:
        tt = [0 for _ in range(2 * 10 ** 5 + 2)]
    for j in range(2 * si - 1, 2 * ti):
        if tt[j] == 0:
            tt[j] = 1
            ans[j] += 1
    cc = ci
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
n, c = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]
x.sort(key=lambda x: [x[-1], x[-2]])
ans = [0 for _ in range(2 * 10 ** 5 + 2)]
cc = -1
for i in range(n):
    si, ti, ci = x[i]
    if ci != cc:
        tt = [0 for _ in range(2 * 10 ** 5 + 2)]
    for j in range(2 * si - 1, 2 * ti):
        if tt[j] == 0:
            tt[j] = 1
            ans[j] += 1
    cc = ci
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
n, c = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]
x.sort(key=lambda x: [x[-1], x[-2]])
ans = [0 for _ in range(2 * 10 ** 5 + 2)]
tt = [0 for _ in range(2 * 10 ** 5 + 2)]
i = 0
ci = x[0][-1]
while(i < n):
    si, ti, ci = x[i]
    for j in range(2 * si - 1, 2 * ti):
        if tt[j] == 0:
            tt[j] = 1
            ans[j] += 1
    i += 1
    if i == n or ci != x[i][-1]:
        tt = [0 for _ in range(2 * 10 ** 5 + 2)]
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
n, c = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]
x.sort(key=lambda x: x[-1])
ans = [0 for _ in range(2 * 10 ** 5 + 2)]
tt = [0 for _ in range(2 * 10 ** 5 + 2)]
i = 0
ci = x[0][-1]
while(i < n):
    si, ti, ci = x[i]
    tt[2 * si - 1] += 1
    tt[2 * ti] -= 1
    i += 1
    if i == n or ci != x[i][-1]:
        ans[0] = tt[0]
        for j in range(1, len(tt)):
            tt[j] += tt[j - 1]
            if tt[j] > 0:
                ans[j] += 1
        tt = [0 for _ in range(2 * 10 ** 5 + 2)]
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, C = map(int, input().split())
    stc = [list(map(int, input().split())) for _ in range(N)]
    st = []
    mxt = 0
    mnt = 0
    while len(stc) > 0:
        s, t, c = stc.pop()
        for i, (ss, tt, cc) in enumerate(stc):
            if c == cc:
                if s == tt:
                    stc.pop(i)
                    stc.append((ss, t, c))
                    break
                elif ss == t:
                    stc.pop(i)
                    stc.append((s, tt, c))
                    break
        else:
            mnt = min(mnt, s - 1)
            mxt = max(mxt, t)
            st.append((s - 1, t))
    cs = [0] * (mxt + 1)
    for s, t in st:
        cs[s] += 1
        cs[t] += -1
    ans = 0
    cc = 0
    for c in cs:
        cc += c
        ans = max(ans, cc)
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, C = map(int, input().split())
    stc = [list(map(int, input().split())) for _ in range(N)]
    st = []
    mxt = 0
    mnt = 0
    while len(stc) > 0:
        s, t, c = stc.pop()
        for i, (ss, tt, cc) in enumerate(stc):
            if c == cc:
                if s == tt:
                    stc.pop(i)
                    stc.append((ss, t, c))
                    break
                elif ss == t:
                    stc.pop(i)
                    stc.append((s, tt, c))
                    break
        else:
            mnt = min(mnt, s - 1)
            mxt = max(mxt, t)
            st.append((s - 1, t))
    ans = 0
    for i in range(mnt, mxt + 1):
        ans = max(ans, sum(1 for s, t in st if s < i <= t))
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
t_max = 10 ** 5

N, C = map(int, input().split())
imos = [[0] * (t_max + 1) for _ in range(C + 1)]
# imos[c][x]:=チャンネルc,時刻xの使用有無
# c: 1-indexed
# x: 1-indexed

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

for c in range(1, C + 1):
    for i in range(1, t_max + 1):
        imos[c][i] += imos[c][i - 1]
        if imos[c][i] > 0 and imos[c][i - 1] == 0:
            imos[c][i - 1] = imos[c][i]

ans = 0
for i in range(1, t_max + 1):
    ans = max(ans, sum(imos[c][i] for c in range(1, C + 1)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
t_max = 10 ** 5

N, C = map(int, input().split())
imos = [[0] * (t_max + 1) for _ in range(C + 1)]
# imos[c][x]:=チャンネルc,時刻xの使用有無
# c: 1-indexed
# x: 1-indexed

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

for c in range(1, C + 1):
    for i in range(1, t_max + 1):
        imos[c][i] += imos[c][i - 1]

for c in range(1, C + 1):
    for i in range(1, t_max + 1):
        x = imos[c][i]
        if x > 0 and imos[c][i - 1] == 0:
            imos[c][i - 1] = x

ans = 0
for i in range(1, t_max + 1):
    ans = max(ans, sum(imos[c][i] for c in range(1, C + 1)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#D問題
N,C=map(int,input().split())
S=[]
T=[]
C=[]
for i in range(N):
    s,t,c=map(int,input().split())
    S.append(s)
    T.append(t)
    C.append(c)
SMAX=max(S)
TMAX=max(T)
Scount=[0 for i in range(TMAX+2)]
Tcount=[0 for i in range(TMAX+2)]
for i in range(N):
    Scount[S[i]]+=1
    Tcount[T[i]]+=1
    for j in range(i):
        if C[j] == C[i]:
            if T[j] == S[i]:
                Tcount[T[i]]-=1
                break
            else:
                pass
count=[]
for i in range(1,TMAX+1):
    if i == 1:
        kari=0
    else:
        kari=count[-1]
    kari+=Scount[i]
    kari-=Tcount[i-1]
    count.append(kari)
print(max(count))

Submission status: Time Limit Exceeded

Solution code:
#D問題
N,C=map(int,input().split())
S=[]
T=[]
C=[]
for i in range(N):
    s,t,c=map(int,input().split())
    S.append(s)
    T.append(t)
    C.append(c)
TMAX=max(T)
count=[]
for i in range(1,TMAX+1):
    if i == 1:
        kari=0
    else:
        kari=count[-1]
    kari+=S.count(i)
    kari-=T.count(i-1)
    count.append(kari)
print(max(count))

Submission status: Time Limit Exceeded

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

channells = {}
for i in range(C+1):
    channells[i] = []
max_end = -1

for i in range(N):
    s,g,c = tv_times[i]
    max_end = max(max_end,g)
    channells[c] += [s,g]

tv_times = []
f = [0 for i in range(max_end+1)]
for cha in channells.keys():
    remove_list = []
    time = channells[cha]
    time.sort()
    for i in range(1,len(time)-1):
        if time[i] == time[i+1]:
            remove_list.append(time[i])
    for i in range(len(remove_list)):
        for j in range(2):
            time.remove(remove_list[i])

    for i in range(len(time)//2):
        f[max(time[2*i]-1,0)] += 1
        f[time[2*i+1]] -= 1

ans = -1
for i in range(1,max_end+1):
    f[i] += f[i-1]
    if ans < f[i]:
        ans = f[i]

# print(f)
print(ans)

Submission status: Time Limit Exceeded

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

channells = {}
for i in range(C+1):
    channells[i] = []
max_end = -1

for i in range(N):
    s,g,c = tv_times[i]
    max_end = max(max_end,g)
    channells[c] += [s,g]

tv_times = []
f = [0 for i in range(max_end+1)]
for cha in channells.keys():
    remove_list = []
    time = channells[cha]
    time.sort()
    for i in range(len(time)//2-1):
        if time[2*i+1] == time[2*i+2]:
            remove_list.append(time[2*i+1])
    for i in range(len(remove_list)):
        time.remove(remove_list[i])
        time.remove(remove_list[i])
    # print(time)
    # print(f)
    for i in range(len(time)//2):
        f[max(time[2*i]-1,0)] += 1
        f[time[2*i+1]] -= 1

ans = -1
for i in range(1,max_end):
    f[i] += f[i-1]
    if ans < f[i]:
        ans = f[i]

# print(f)
print(ans)

Submission status: Time Limit Exceeded

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

channells = {}
for i in range(C+1):
    channells[i] = []
max_end = -1

for i in range(N):
    s,g,c = tv_times[i]
    max_end = max(max_end,g)
    channells[c] += [s,g]

tv_times = []
f = [0 for i in range(max_end+1)]
for cha in channells.keys():
    remove_list = []
    time = channells[cha]
    time.sort()
    for i in range(len(time)-1):
        if time[i] == time[i+1]:
            remove_list.append(time[i])
    for i in range(len(remove_list)):
        time.remove(remove_list[i])
        time.remove(remove_list[i])
    # print(time)
    # print(f)
    for i in range(len(time)//2):
        f[max(time[2*i]-1,0)] += 1
        f[time[2*i+1]] -= 1

ans = -1
for i in range(1,max_end):
    f[i] += f[i-1]
    if ans < f[i]:
        ans = f[i]

# print(f)
print(ans)