Задача: На экране рисуются полосы

Question

Экран представляет собой прямоугольник а пикселей в высоту и в пикселей в ширину. Каждый шаг на экране рисуются полосы пикселей цветом с(либо вертикально либо горизонтально).Если пиксель уже имеет какой-то цвет, то он перекрашивается. Изначально экран заполнен цветом 0, этим цветом рисоваться не планируется. Таких операций будет произведено N штук. Формат входных данных: В первой строке даны размеры экрана А и В(1<=A<=B<=10^9), число используемых цветом N(1<=N<=3x10^5) и количество полос q(1<=q<=3x10^5) В следующих q строках даны полосы в порядке их появления. Каждая полоса задается тройкой чисел: type n color, где type = 1 означает закрашивание строки, а type =2 – столбца. N означает порядковый номер строки или столбца, а color – используемый цвет. Формат выходных данных: Для каждого цвета от 1 до N вывески количество пикселей данного цвета.

Пример 1:
Ввод:
4 6 5 7
1 1 1
2 2 4
1 3 3
2 4 2
1 1 2
1 1 5
2 1 3
Вывод:
0 3 8 2 5

Пример 2: Ввод: 500000000 500000000 3 5
1 1 2
1 2 3
1 3 3
1 4 3
1 5 3
Вывод: 0 500000000 200000000

Вот рабочий алгоритм, но он съедает очень много памяти из-за создания массива размером a*b. Что при числах от 10**5 уже не проходит тесты. Как можно улучшить, чтобы обойти это?

b, a, N, q = map(int, input().split())

matrix=[0]*b*a
for i in range(q):
    typ,n,color =map(int, input().split())
    if typ == 1:
        for k in range(a):
            matrix[(n-1)*a+k] = color

    if typ == 2:
        for k in range(b):
            matrix[(n-1)+k*b] = color
matrix= [i for i in matrix if i != 0]
numbers=[]
for i in range(1,N+1):
   numbers.append(matrix.count(i))
print(' '.join(map(str, numbers)))

Answer 1

Если одна и та же строка закрашена много раз, учитывать надо только последнюю закраску. Далее будем считать что строки и столбцы не повторяются.

Сколько пикселов закрасит очередная строка? Ширина экрана минус число закрашенных столбцов после неё.

Будет обрабатывать штрихи в обратном порядке.

ab[0] - ширина экрана, ab[1] - высота экрана.

painted[0] - множество закрашенных столбцов, painted[1] - множество закрашенных строк.

colors[c - 1] - число пикселей цвета c.

*ab, n, q = map(int, input().split())

s = tuple(tuple(map(int, input().split())) for _ in range(q))

painted = set(), set()
colors = [0] * n
for t, x, c in reversed(s):
    if x not in painted[1 - (t - 1)]:
        painted[1 - (t - 1)].add(x)
        colors[c - 1] += ab[1 - (t - 1)] - len(painted[t - 1])

print(*colors)

$ python paint.py << EOF
4 6 5 7
1 1 1
2 2 4
1 3 3
2 4 2
1 1 2
1 1 5
2 1 3
EOF
0 3 8 2 5

$ python paint.py << EOF
500000000 500000000 3 5
1 1 2
1 2 3
1 3 3
1 4 3
1 5 3
EOF
0 500000000 2000000000

БЛОГ НА HUSL

Задача: На экране рисуются полосы

Ответы (1 шт):