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:
N, C, *STC = [int(_) for _ in open(0).read().split()]
STC = [(s, t, c) for s, t, c in zip(STC[::3], STC[1::3], STC[2::3])]
STC.sort()

class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_right(self, p, v):  # apply operator from the right side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(dat[p], v)
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_left(self, p, v):  # apply operator from the left side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(v, dat[p])
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        vl = vr = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                vl = f(vl, dat[l])
                l += 1
            if r & 1:
                r -= 1
                vr = f(dat[r], vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)

ti = (10 ** 10, -1)
st = SegmentTree([(10 ** 10, i) for i in range(C + 1)], min, ti)
s, t, c = STC[0]
st.update(c, (t, c))
ans = 1
for s, t, c in STC[1:]:
    if s >= st.query(c, c + 1)[0]:
        st.update(c, (t, c))
    else:
        t2, c2 = st.query(0, C + 1)
        if t2 >= s:
            ans += 1
        st.update(c, (t, c))
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop,heappush

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

stc = sorted(stc,key=lambda x:x[2])
stc = sorted(stc)
count=0
for i in range(N-1):
  if stc[i][2]==stc[i+1][2] and stc[i][1]==stc[i+1][0]:
    stc[i+1] = (stc[i][0],stc[i+1][1],stc[i][2])
    stc[i] = (10**9,-1,-1)
    count += 1
    
if count > 0:
  stc = sorted(stc)[:-count]
  N=len(stc)

machines=[]

MAX=0
for i in range(N):
  s,t,c=stc[i]
  if i == 0:
    heappush(machines,(t,c))
    continue
  t0,c0 = heappop(machines)
  if s>t0 or (s>=t0 and c==c0):
    heappush(machines,(t,c))
    continue
  else:
    heappush(machines,(t0,c0))
    heappush(machines,(t,c))
  MAX = max(MAX,len(machines))

print(MAX)

Submission status: Wrong Answer

Solution code:
from heapq import heappop,heappush

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

MAX=0
for i in range(N):
  s,t,c=stc[i]
  if i == 0:
    heappush(machines,(t,c))
    continue
  t0,c0 = heappop(machines)
  if s>t0 or (s>=t0 and c==c0):
    heappush(machines,(t,c))
    continue
  else:
    heappush(machines,(t0,c0))
    heappush(machines,(t,c))
  MAX = max(MAX,len(machines))

print(MAX)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, C = in_nn()
    stc = in_nl2(N)

    channel = [[] for _ in range(C)]
    for i in range(N):
        s, t, c = stc[i]
        channel[c - 1].append((s, t))

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

    channel2 = [[] for _ in range(C)]
    for c in range(C):
        for i in range(len(channel[c])):
            s, t = channel[c][i]
            if channel2[c]:
                pre_s, pre_t = channel2[c][-1]
                if pre_t == s:
                    channel2[c][-1] = (pre_s, t)
                else:
                    channel2[c].append((s, t))
            else:
                channel2[c].append((s, t))

    stc2 = []
    for c in range(C):
        for i in range(len(channel2[c])):
            s, t = channel2[c][i]
            stc2.append((s, t, c))

    tv = []
    for i in sorted(range(len(stc2)), key=lambda x: (stc2[x][0])):
        s, t, c = stc2[i]

        search_tv = -1
        for j in range(len(tv)):
            end, chan = tv[j]
            if chan == c:
                if end == s:
                    search_tv = j
                    break
            else:
                if end < s:
                    if search_tv == -1:
                        search_tv = j

        if search_tv == -1:
            tv.append((t, c))
        else:
            tv[j] = (t, c)

    print(len(tv))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, C = in_nn()
    stc = in_nl2(N)

    tv = []
    for i in sorted(range(N), key=lambda x: (stc[x][0])):
        s, t, c = stc[i]

        search_tv = -1
        for j in range(len(tv)):
            end, chan = tv[j]
            if chan == c:
                if end == s:
                    search_tv = j
                    break
            else:
                if end < s:
                    if search_tv == -1:
                        search_tv = j

        if search_tv == -1:
            tv.append((t, c))
        else:
            tv[j] = (t, c)

    print(len(tv))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, C = in_nn()
    stc = in_nl2(N)

    tv = [(0, 0)]
    for i in sorted(range(N), key=lambda x: (stc[x][0])):
        s, t, c = stc[i]

        max_end = -1
        search_tv = -1
        for j in range(len(tv)):
            end, chan = tv[j]
            if chan == c:
                if end <= s:
                    if end > max_end:
                        max_end = end
                        search_tv = j
            else:
                if end < s:
                    if end > max_end:
                        max_end = end
                        search_tv = j

        if search_tv == -1:
            tv.append((t, c))
        else:
            tv[j] = (t, c)

    print(len(tv))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, C = in_nn()
    stc = in_nl2(N)

    tv = [(0, 0)]
    for i in sorted(range(N), key=lambda x: (stc[x][1], stc[x][0])):
        s, t, c = stc[i]

        max_end = -1
        search_tv = -1
        for j in range(len(tv)):
            end, chan = tv[j]
            if chan == c:
                if end <= s:
                    if end > max_end:
                        max_end = end
                        search_tv = j
            else:
                if end < s:
                    if end > max_end:
                        max_end = end
                        search_tv = j

        if search_tv == -1:
            tv.append((t, c))
        else:
            tv[j] = (t, c)

    print(len(tv))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, C = in_nn()
    stc = in_nl2(N)

    tv = [(0, 0)]
    for i in sorted(range(N), key=lambda x: stc[x][1]):
        s, t, c = stc[i]

        max_end = -1
        search_tv = -1
        for j in range(len(tv)):
            end, chan = tv[j]
            if chan == c:
                if end <= s:
                    if end > max_end:
                        max_end = end
                        search_tv = j
            else:
                if end < s:
                    if end > max_end:
                        max_end = end
                        search_tv = j

        if search_tv == -1:
            tv.append((t, c))
        else:
            tv[j] = (t, c)

    print(len(tv))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq
n, cc = map(int, raw_input().split())
times = [map(int, raw_input().split()) for _ in range(n)]
times.sort(key = lambda x:(x[1], x[0]))
heap = []
m = 0
for el in times:
	s,e,c = el
	s*=2
	s-=1
	e*=2
	while(heap and heap[0][0] <= s):
		heapq.heappop(heap)
	heapq.heappush(heap, (e,c))
	m = max(m, len(heap))
print m

Submission status: Wrong Answer

Solution code:
import heapq
n, cc = map(int, raw_input().split())
times = [map(int, raw_input().split()) for _ in range(n)]
times.sort(key = lambda x:(x[1], x[0]))
heap = []
m = 0
for el in times:
	s,e,c = el
	while(heap and heap[0][0] <= (s - (1 if c != heap[0][1] else 0) )):
		heapq.heappop(heap)
	heapq.heappush(heap, (e,c))
	m = max(m, len(heap))
print m

Submission status: Wrong Answer

Solution code:
import heapq
n, cc = map(int, raw_input().split())
times = [map(int, raw_input().split()) for _ in range(n)]
times.sort(key = lambda x:(x[1], x[0]))
heap = []
m = 0
for el in times:
	s,e,c = el
	while(heap and heap[0][0] <= (s + (1 if c != heap[0][1] else 0) )):
		heapq.heappop(heap)
	heapq.heappush(heap, (e,c))
	m = max(m, len(heap))
print m

Submission status: Wrong Answer

Solution code:
import heapq
n, cc = map(int, raw_input().split())
times = [map(int, raw_input().split()) for _ in range(n)]
times.sort(key = lambda x:(x[1], x[0]))
heap = []

m = 0
for el in times:
	s,e,c = el
	while(heap and heap[0] <= s):
		heapq.heappop(heap)
	heapq.heappush(heap, e+1)
	m = max(m, len(heap))
print m

Submission status: Wrong Answer

Solution code:
n,c=map(int,input().split())
a=[]
tf=0
for _ in range(n):
  s,t,ch=map(int,input().split())
  a+=[(ch,s,t)]
a=sorted(a)
flag=a[0][0]
ans=[0]*(10**5+1)
tf=0
for ch,s,t, in a:
  if ch==flag and tf==s:ans[s]+=1
  else:ans[s-1]+=1
  ans[t]-=1
  t=tf
  flag=ch
for i in range(10**5):
  ans[i+1]+=ans[i]
print(max(ans))

Submission status: Wrong Answer

Solution code:
import bisect
n, C = map(int, input().split())

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

for i in range(C):
    for j in range(U):
        channels[i][j+1] += channels[i][j]

schedules = []
for i in range(C):
    L = None
    for j in range(U+1):
        if channels[i][j] and L is None:
            L = j-1
            continue

        if not channels[i][j] and L is not None:
            schedules.append((L, j))
            L = None

schedules.sort()
channel = [-2]*(C+1)
for L, R in schedules:
    idx = bisect.bisect_right(channel, L)-1
    channel[idx] = R
print(C-bisect.bisect_left(channel, -1)+1)

Submission status: Wrong Answer

Solution code:
import bisect
n, C = map(int, input().split())

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

for i in range(C):
    for j in range(U):
        channels[i][j+1] += channels[i][j]

schedules = []
for i in range(C):
    L = None
    for j in range(U+1):
        if 0 < channels[i][j] and L is None:
            L = j
            continue

        if 0 == channels[i][j] and L is not None:
            schedules.append((L, j-1))
            L = None

schedules.sort(key=lambda x: x[1])
channel = [-1]*(C+1)
for L, R in schedules:
    idx = bisect.bisect_left(channel, L)-1
    channel[idx] = R
print(C-bisect.bisect_left(channel, 0)+1)

Submission status: Wrong Answer

Solution code:
import bisect
n, C = map(int, input().split())

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

for i in range(C):
    for j in range(U):
        channels[i][j+1] += channels[i][j]

schedules = []
for i in range(C):
    L = None
    for j in range(U+1):
        if 0 < channels[i][j] and L is None:
            L = j
            continue

        if 0 == channels[i][j] and L is not None:
            schedules.append((L, j-1))
            L = None
            
schedules.sort()
channel = [-1]*(C+1)
for L, R in schedules:
    idx = bisect.bisect_left(channel, L)-1
    channel[idx] = R
print(C-bisect.bisect_left(channel, 0)+1)

Submission status: Wrong Answer

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

n,c=map(int,readline().split())
#m=2*10**5
m=200
stc=[list(map(int,l.split())) for l in read().splitlines()]
cht=[[0]*(m+1) for _ in range(c)]
for e in stc:
  cht[e[2]-1][2*e[0]-1:2*e[1]]=[1 for _ in range(2*e[1]-2*e[0]+1)]
mnr=0
for i in range(1,m+1):
  mnr=max(mnr,sum(cht[ch][i] for ch in range(c)))
print(mnr)

Submission status: Wrong Answer

Solution code:
n, c = map(int, input().split())
program = [[] for _ in range(c)]

for i in range(n):
  s, t, cc = map(int, input().split())
  program[cc-1].append((s, t))

count = [0]*(10**5+1)
judge = True
for i in range(c):
  program[i].sort()
  l = len(program[i])
  for j in range(l-1):
    if judge:
      count[program[i][j][0]-1] += 1
    if program[i][j][1] == program[i][j+1][0]:
      judge = False
    else:
      judge = True
    if judge:
      count[program[i][j][1]] -= 1
  if l == 0:
    continue
  if judge:
    count[program[i][l-1][0]-1] += 1
  count[program[i][l-1][1]] -= 1

ans = 0
for i in range(10**5+1):
  if i != 0:
    count[i] += count[i-1]
  if ans < count[i]:
    ans = count[i]
print(ans)

Submission status: Wrong Answer

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

dd=defaultdict(lambda: [0]*(10**5+1))
for s,t,c in s:
  for i in range(s-1,t+1):
    dd[c][i]=1
ans=0
for i in range(10**5+1):
  cnt=0
  for ch in range(C+1):
    if dd[ch][i]==1:
      cnt+=1
  ans=max(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, C, *STC = map(int, read().split())

    P = [[] for _ in range(C)]
    for i, (s, t, c) in enumerate(zip(*[iter(STC)] * 3)):
        P[c - 1].append((s, t))

    M = 10 ** 5
    vec = [0] * (M + 2)
    for i in range(C):
        for j, (s, t) in enumerate(P[i]):
            if j > 0 and s == P[i][j - 1][1]:
                vec[s] += 1
                vec[t] += -1
            else:
                vec[s - 1] += 1
                vec[t] += -1

    vec = list(accumulate(vec))

    print(max(vec))
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

N, C = map(int, sys.stdin.readline().split())

# 同一チャンネルならtとsが連続していても1台で録画できる
# そのため、通常のimos法ではなく、録画開始・終了のチャンネルを保持する
times = [[set() for _ in range(2 * 10**5 + 5)], [set() for _ in range(2 * 10**5 + 5)]]
for _ in range(N):
    s, t, c = map(int, sys.stdin.readline().split())
    times[0][2 * s - 1].add(c)
    times[1][2 * t].add(c)

ans = 0
recording = set()
for i in range(2 * 10**5 + 5):
    recording -= times[1][i]
    recording |= times[0][i]
    ans = max(ans, len(recording))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

N, C = map(int, sys.stdin.readline().split())

# 同一チャンネルならtとsが連続していても1台で録画できる
# そのため、通常のimos法ではなく、録画開始・終了のチャンネルを保持する
times = [[set() for _ in range(2 * 10**5 + 2)], [set() for _ in range(2 * 10**5 + 2)]]
for _ in range(N):
    s, t, c = map(int, sys.stdin.readline().split())
    times[0][2 * s - 1].add(c)
    times[1][2 * t].add(c)

ans = 0
recording = set()
for i in range(2 * 10**5 + 1):
    recording -= times[1][i]
    recording |= times[0][i]
    ans = max(ans, len(recording))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

N, C = map(int, sys.stdin.readline().split())

# 同一チャンネルならtとsが連続していても1台で録画できる
# そのため、通常のimos法ではなく、録画開始・終了のチャンネルを保持する
times = [[set() for _ in range(2 * 10**5 + 2)], [set() for _ in range(2 * 10**5 + 2)]]
for _ in range(N):
    s, t, c = map(int, sys.stdin.readline().split())
    times[0][2 * s - 1].add(c)
    times[1][2 * t].add(c)

ans = 0
recording = set()
for i in range(2 * 10**5 + 1):
    recording |= times[0][i]
    recording -= times[1][i]
    ans = max(ans, len(recording))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

N, C = map(int, sys.stdin.readline().split())

# 同一チャンネルならtとsが連続していても1台で録画できる
# そのため、通常のimos法ではなく、録画開始・終了のチャンネルを保持する
times = [[set() for _ in range(2 * 10**5 + 2)], [set() for _ in range(2 * 10**5 + 2)]]
for _ in range(N):
    s, t, c = map(int, sys.stdin.readline().split())
    times[0][2 * s - 1].add(c)
    times[1][2 * t].add(c)

ans = 0
recording = set()
for i in range(2 * 10**5 + 1):
    recording |= times[0][i]
    ans = max(ans, len(recording))
    recording -= times[1][i]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

N, C = map(int, sys.stdin.readline().split())

# 同一チャンネルならtとsが連続していても1台で録画できる
# そのため、通常のimos法ではなく、録画開始・終了のチャンネルを保持する
times = [[set() for _ in range(10**5 + 2)], [set() for _ in range(10**5 + 2)]]
for _ in range(N):
    s, t, c = map(int, sys.stdin.readline().split())
    times[0][s].add(c)
    times[1][t].add(c)

ans = 0
recording = set()
for i in range(10**5):
    recording |= times[0][i]
    ans = max(ans, len(recording))
    recording -= times[1][i]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

N, C = map(int, sys.stdin.readline().split())

# 同一チャンネルならtとsが連続していても1台で録画できる
# そのため、通常のimos法ではなく、録画開始・終了のチャンネルを保持する
times = [[set() for _ in range(10**5 + 2)], [set() for _ in range(10**5 + 2)]]
for _ in range(N):
    s, t, c = map(int, sys.stdin.readline().split())
    times[0][s-1].add(c)
    times[1][t].add(c)

ans = 0
recording = set()
for i in range(10**5):
    recording -= times[1][i]
    recording |= times[0][i]
    ans = max(ans, len(recording))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

N, C = map(int, sys.stdin.readline().split())

# 同一チャンネルならtとsが連続していても1台で録画できる
# そのため、通常のimos法ではなく、録画開始・終了のチャンネルを保持する
times = [[set() for _ in range(10**5 + 2)], [set() for _ in range(10**5 + 2)]]
for _ in range(N):
    s, t, c = map(int, sys.stdin.readline().split())
    times[0][s].add(c)
    times[1][t+1].add(c)

ans = 0
recording = set()
for i in range(10**5):
    recording -= times[1][i]
    recording |= times[0][i]
    ans = max(ans, len(recording))

print(ans)

Submission status: Wrong Answer

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

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

stc.sort()

lst = []
hq = [[-1, -1]]
heapq.heapify(hq)
ans = 1
for i in range(N):
    p = stc[i]
    q = heapq.heappop(hq)
    if p[0] < q[0]:
        heapq.heappush(hq, q)
        ans += 1
    elif p[0] == q[0]:
        lst = []
        jdg2 = True
        lst.append(q)
        while p[0] == q[0] and p[2]>= q[1]:
            if p[2] == q[1]:
                jdg2 = False
            else:
                lst.append(q)
            if hq: q = heapq.heappop(hq)
            else: break
        if jdg2: ans += 1

        for k in lst:
            heapq.heappush(hq, k)

    heapq.heappush(hq, [p[1], p[2]])

print(ans)

Submission status: Wrong Answer

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

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

stc.sort()

lst = []
hq = [[-1, -1]]
heapq.heapify(hq)
ans = 1
for i in range(N):
    p = stc[i]
    q = heapq.heappop(hq)
    if p[0] > q[0]:
        heapq.heappush(hq, [p[1], p[2]])
    elif p[0] == q[0]:
        lst = []
        jdg2 = True
        lst.append(q)
        while p[0] == q[0] and p[2]>= q[1]:
            if p[2] == q[1]:
                heapq.heappush(hq, [p[1], p[2]])
                jdg2 = False
            else:
                lst.append(q)
            if hq: q = heapq.heappop(hq)
            else: break
        if jdg2: ans += 1
        for k in lst:
            heapq.heappush(hq, k)
    else:
        heapq.heappush(hq, q)
        heapq.heappush(hq, [p[1], p[2]])
        ans += 1

print(ans)

Submission status: Wrong Answer

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

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

stc.sort()

lst = []
hq = [[-1, -1]]
heapq.heapify(hq)
ans = 1
for i in range(N):
    p = stc[i]
    q = heapq.heappop(hq)
    if p[0] > q[0] and p[0] != q[0]:
        heapq.heappush(hq, [p[1], p[2]])
    elif p[0] == q[0]:
        jdg2 = True
        lst.append(q)
        while p[0] == q[0] and p[2]>= q[1]:
            if p[2] == q[1]:
                heapq.heappush(hq, [p[1], p[2]])
                jdg2 = False
            else:
                lst.append(q)
            if hq: q = heapq.heappop(hq)
            else: break
        if jdg2: ans += 1
        for k in lst:
            heapq.heappush(hq, k)
    else:
        heapq.heappush(hq, q)
        heapq.heappush(hq, [p[1], p[2]])
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import queue

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def ddd(al, c):
	rcq = queue.Queue()
	for _ in range(c):
		rcq.put(0)
	for st, ed in al:
		earliest = rcq.get()
		#pa((earliest,st))
		if earliest >= st-0.5:
			return False
		rcq.put(ed)
	return True

def main():
	#a = int(input())
	n, c = tin()
	#s = input()
	dd=[[] for _ in range(c)]
	for _ in range(n):
		s, t, cv = tin()
		dd[cv-1].append((s,t))
	aal=[]
	for cl in dd:
		if len(cl)==0:
			continue
		cl.sort()
		sa, ta = cl[0]
		for s, t in cl[1:]:
			if ta == s:
				ta = t
			else:
				aal.append((sa, ta))
				sa,ta = s, t
		else:
			aal.append((sa, ta))
			
	#aal = [list(tin()) for _ in range(n)]
	aal.sort()
	pa(aal)
	for i in range(1, c+1):
		is_ok = ddd(aal, i)
		#pa(i)
		if is_ok:
			return i
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys
import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def ddd(al, c):
	rcq = queue.Queue()
	for _ in range(c):
		rcq.put(0)
	for st, ed in al:
		earliest = rcq.get()
		#pa((earliest,st))
		if earliest >= st-0.5:
			return False
		rcq.put(ed)
	return True

def main():
	#a = int(input())
	n, c = tin()
	#s = input()
	dd=[[] for _ in range(c)]
	for _ in range(n):
		s, t, cv = tin()
		dd[cv-1].append((s,t))
	aal=[]
	for cl in dd:
		if len(cl)==0:
			continue
		sa, ta = cl[0]
		for s, t in cl[1:]:
			if ta == s:
				ta = t
			else:
				aal.append((sa, ta))
				sa,ta = s, t
		else:
			aal.append((sa, ta))
			
	#aal = [list(tin()) for _ in range(n)]
	aal.sort()
	#pa(aal)
	for i in range(1, c+1):
		is_ok = ddd(aal, i)
		#pa(i)
		if is_ok:
			return i
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys
import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def ddd(al, c):
	rcq = queue.Queue()
	for _ in range(c):
		rcq.put(0)
	for st, ed in al:
		earliest = rcq.get()
		#pa((earliest,st))
		if earliest >= st-0.5:
			return False
		rcq.put(ed)
	return True

def main():
	#a = int(input())
	n, c = tin()
	#s = input()
	dd=[[] for _ in range(c)]
	for _ in range(n):
		s, t, c = tin()
		dd[c-1].append((s,t))
	aal=[]
	for cl in dd:
		if len(cl)==0:
			continue
		sa, ta = cl[0]
		for s, t in cl[1:]:
			if ta == s:
				ta = t
			else:
				aal.append((sa, ta))
				sa,ta = s, t
		else:
			aal.append((sa, ta))
			
	#aal = [list(tin()) for _ in range(n)]
	aal.sort()
	#pa(aal)
	for i in range(1, c+1):
		is_ok = ddd(aal, i)
		if is_ok:
			return i
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys
import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def ddd(al, c):
	rcq = queue.Queue()
	for _ in range(c):
		rcq.put(0)
	for st, ed, nc in al:
		earliest = rcq.get()
		#pa((earliest,st))
		if earliest+0.5 > st:
			return False
		rcq.put(ed)
	return True

def main():
	#a = int(input())
	n, c = tin()
	#s = input()
	aal = [list(tin()) for _ in range(n)]
	aal.sort()
	for i in range(1, c+1):
		is_ok = ddd(aal, i)
		if is_ok:
			return i
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import heapq
N, C = map(int, input().split())
stc = [list(map(int, input().split())) for _ in range(N)]

stc.sort()
hq = [[-1, -1]]
heapq.heapify(hq)
ans = 1
for i in range(N):
    p = stc[i]
    q = heapq.heappop(hq)
    if p[0]-0.5 >= q[0] or p[2] == q[1]:
        heapq.heappush(hq, [p[1], p[2]])
    else:
        heapq.heappush(hq, q)
        heapq.heappush(hq, [p[1], p[2]])
        ans += 1
print(ans)