Submission #525117
Source Code Expand
class SegmentTree():
"""Segment Tree class"""
MAX_VAL = 10 ** 10
def __init__(self, n):
self.n = 1
while self.n < n:
self.n *= 2
self.ary = [self.MAX_VAL] * (self.n * 2 - 1)
def update(self, k, a):
pos = self.n - 1 + k
self.ary[pos] = a
while pos > 0:
pos = (pos - 1) // 2
self.ary[pos] = min(self.ary[pos * 2 + 1], self.ary[pos * 2 + 2])
def __getvalue(self, a, b, k, l, r):
if b < l or r < a:
return self.MAX_VAL
elif a <= l and r <= b:
return self.ary[k]
else:
return min(
self.__getvalue(a, b, 2 * k + 1, l, (l + r) // 2),
self.__getvalue(a, b, 2 * k + 2, (l + r) // 2 + 1, r)
)
def getvalue(self, a, b):
return self.__getvalue(
a, b, 0, 0, self.n - 1
)
if __name__ == '__main__':
N, M = map(int, input().split())
st_list = []
room = [0] * (N + 1)
for _ in range(M):
s, t = map(int, input().split())
st_list.append((s - 1, t - 1))
room[s - 1] += 1
room[t] -= 1
for i in range(N):
room[i + 1] += room[i]
st = SegmentTree(N)
for i, e in enumerate(room[:-1]):
st.update(i, e)
answer = []
for i, (s, t) in enumerate(st_list, 1):
if st.getvalue(s, t) >= 2:
answer.append(i)
print(len(answer))
for e in answer:
print(e)
Submission Info
Submission Time |
|
Task |
B - ドキドキデート大作戦高橋君 |
User |
yousack728 |
Language |
Python (3.4.2) |
Score |
0 |
Code Size |
1559 Byte |
Status |
TLE |
Exec Time |
2045 ms |
Memory |
42904 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
All |
Score / Max Score |
0 / 0 |
0 / 30 |
0 / 70 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt |
Subtask1 |
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt |
All |
subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_sample_01.txt |
AC |
127 ms |
6924 KB |
subtask0_sample_02.txt |
AC |
96 ms |
6820 KB |
subtask0_sample_03.txt |
AC |
96 ms |
6964 KB |
subtask1_01.txt |
TLE |
2039 ms |
33312 KB |
subtask1_02.txt |
TLE |
2039 ms |
33324 KB |
subtask1_03.txt |
TLE |
2038 ms |
27696 KB |
subtask1_04.txt |
TLE |
2039 ms |
26888 KB |
subtask1_05.txt |
TLE |
2039 ms |
26896 KB |
subtask1_06.txt |
AC |
122 ms |
6944 KB |
subtask1_07.txt |
AC |
95 ms |
6812 KB |
subtask1_08.txt |
AC |
94 ms |
6812 KB |
subtask1_09.txt |
AC |
95 ms |
6820 KB |
subtask2_01.txt |
TLE |
2045 ms |
39752 KB |
subtask2_02.txt |
TLE |
2042 ms |
42904 KB |
subtask2_03.txt |
AC |
103 ms |
6868 KB |
subtask2_04.txt |
AC |
106 ms |
6816 KB |
subtask2_05.txt |
AC |
104 ms |
6816 KB |
subtask2_06.txt |
AC |
103 ms |
6812 KB |
subtask2_07.txt |
AC |
102 ms |
6816 KB |
subtask2_08.txt |
TLE |
2040 ms |
33908 KB |