Stack Overflow на русском Asked by Mswork6 on November 14, 2020
Сегодня решал олимпиаду и одной из задач была задача на списки. Я ее решил, но по времени некоторые тесты не проходили. Я как мог, код оптимизировал, но все равно часть тестов код не проходил. Как я над не не скакал, дальше как то сжать не смог. Но интерес все равно остался: как можно оптимизировать мой код и ускорить выполнение программы?
Условие задачи:
Слияние отрезков
Даны два отсортированных массива A, B. Нужно обработать запросы следующего вида:
l r – Удалить подотрезок A[l, r], добавить его в конец B, и затем отсортировать B.
l r – Удалить подотрезок B[l, r], добавить его в конец A, и затем отсортировать A.
Необходимо вывести получившиеся массивы A, B.
Формат входных данных
Первая строка ввода содержит одно целое число N (0 ≤ N ≤ 5*105) – размер массива A.Вторая строка содержит N целых чисел ai (1 ≤ a1 ≤ a2 ≤ … ≤ an ≤ 109) – содержимое массива A.
Третья строка ввода содержит одно целое число M (0 ≤ M ≤ 5*105) – размер массива B.
Четвёртая строка содержит M целых чисел bi (1 ≤ b1 ≤ b2 ≤ … ≤ bm ≤ 109) – содержимое массива B.
Пятая строка ввода содержит одно целое число Q (1 ≤ Q ≤ 9*105) – число запросов.
Следующие Q строк содержат по три целых числа t, l, r (t равно 1 или 2, 1 ≤ l ≤ r) – описание очередного запроса.
Гарантируется, что все запросы корректны, то есть при t = 1 всегда существует A[l, r] и при t = 2 всегда существует B[l, r].
Формат результата
В первой строке вывода должно быть одно целое число N’ – итоговый размер массива A.Во второй строке вывода должны быть N’ целых чисел – содержимое итогового массива A.
В третьей строке вывода должно быть одно целое число M’ – итоговый размер массива B.
В четвёртой строке вывода должны быть M’ целых чисел- содержимое итогового массива B.
Примеры
Входные данные
4
1 3 5 7
5
2 4 6 7 8
5
1 1 1
2 2 4
2 1 3
1 1 7
2 2 5
Результат работы
6
2 3 4 5 7 8
3
1 6 7
Мой код:
l1 = int(input())
A = list(map(int, input().split()))
l2 = int(input())
B = list(map(int, input().split()))
Q = int(input())
for i in range (Q):
C = list(map(int, input().split()))
if C[0] == 1:
e = C[1]-1
for i in range(C[1]-1, C[2]):
B.append(A[e])
A.remove(A[e])
B.sort()
A.sort()
elif C[0] == 2:
d = C[1]-1
for i in range(C[1]-1, C[2]):
A.append(B[d])
B.remove(B[d])
A.sort()
B.sort()
C = []
l1 = len(A)
l2 = len(B)
print(l1)
for i in range(len(A)):
print(A[i], end = " ")
print("")
print(l2)
for i in range(len(B)):
print(B[i], end = " ")
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP