TransWikia.com

Задача со списками на питоне

Stack Overflow на русском Asked by Mswork6 on November 14, 2020

Сегодня решал олимпиаду и одной из задач была задача на списки. Я ее решил, но по времени некоторые тесты не проходили. Я как мог, код оптимизировал, но все равно часть тестов код не проходил. Как я над не не скакал, дальше как то сжать не смог. Но интерес все равно остался: как можно оптимизировать мой код и ускорить выполнение программы?

Условие задачи:

Слияние отрезков
Даны два отсортированных массива A, B. Нужно обработать запросы следующего вида:

  1. l r – Удалить подотрезок A[l, r], добавить его в конец B, и затем отсортировать B.

  2. 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 = " ")

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP