How to increase script performance?

Question

Python

Artist
(Time: 1 sec. Memory: 16 MB Difficulty: 26%)

A famous artist decided to paint a new masterpiece. After many days of hard work, he wanted to explore his creation. The artist recalled that the picture was painted as follows: first, a white canvas was taken, having the shape of a rectangle with a width w and a height h. Then the artist drew on this canvas n rectangles with sides parallel to the sides of the canvas and vertices located in integer coordinates. Help the artist determine the area of ​​the unpainted part of the canvas.

Input data

The first line of the input file INPUT.TXT contains two natural numbers w and h (1 ≤ w, h ≤ 100). The second line contains an integer n (0 ≤ n ≤ 5000) – the number of rectangles. The next n lines contain information about all rectangles. Each line describes one rectangle as four numbers x1, y1, x2, y2 , where (x1, y1) and (x2, y2) are the coordinates of the upper left and lower right corners of the rectangle, respectively.

Output

Output to the output file OUTPUT.TXT a single integer - the area of ​​the unpainted part of the canvas.

Input and output to files is optional. enough input(), print()
How do I calculate the complexity of the algorithm? And how to optimize? third-party libraries cannot be used
Here's what I got:

w,h = input().split()
w = int(w)
k = 0
h = int(h)
sq = []
count = int(input())
arr = [[0]*h for i in range(w)]
for i in range(count):
  square = [int(l) for l in input().split()]
  for i in range(square[0],square[2]):
    for j in range(square[1],square[3]):
      arr[i][j] = 1

for i in arr:
  for j in i:
    if j==0:
      k += 1
print(k)

In one of the tests, the task does not pass in terms of speed. Although if you use PyPy3, then everything works

Answer 1

The most obvious option is to reduce the number of passes through the array.
You don't need the second pass at all, because already on the first one you can count the number of "painted" points (if the point is not painted over yet, paint over it and increase the counter, otherwise go to the next one). Having the number of "filled" points and the area of ​​the canvas, the calculation is reduced to one action, and the complexity of the algorithm is halved.
If I'm not confusing anything, then it will turn out something like this

w,h = input().split()
w = int(w)
k = 0
h = int(h)
canvasArea = w * h
count = int(input())
arr = [[0]*h for i in range(w)]
for i in range(count):
  square = [int(l) for l in input().split()]
  for i in range(square[0],square[2]):
    for j in range(square[1],square[3]):
      if arr[i][j]==0:
        k += 1
        arr[i][j] = 1
  print(canvasArea - k)

PS A word of advice about naming variables: if you're ever going to do programming outside of the competition, then instead of w, h, k and arr, you should use something like width, height, filledCount, canvas. Since in a slightly larger code it will be much more difficult to understand what all these one-letter variables mean.

Answer 2

Problem analysis on Reddit https://www.reddit.com/comments/zaa0v .
Adapted to the case specified in the condition:
the rectangle is defined by the values ​​(x1, y1, x2, y2), where (x1, y1) is the upper left corner, (x2, y2) is the lower right corner.

x1,y1───────────┐
    │           │
    │           │
    │           │
    │           │
    └───────────x2,y2

The algorithm is as follows: we find the sum of the areas of all rectangles and subtract this amount from the area of ​​the canvas.
The area of ​​the rectangle, in our case, is (x2 - x1) * (y1 - y2).
Case 1. Rectangles do not intersect.

Прямоугольники (0,3,4,0), (4,7,7,3) и (7,3,10,0) будут выглядеть примерно так:
        * * * 
        * * * 
        * * *
        * * *
* * * *       * * *
* * * *       * * *
* * * *       * * *

The total area of ​​these three rectangles is easy to calculate, it's just the sum of the areas of each individual rectangle: (4 * 3) + (3 * 4) + (3 * 3)
Case 2. Rectangles intersect, 2 rectangles have a common intersection.

Рассмотрим три прямоугольника (0,3,4,0), (2,5,5,1) и (4,7,7,4):
        * * * 
        * * * 
    * * + * * 
    * * *     
* * + + *      
* * + + *      
* * * *

You can see that the rectangles intersect (the areas where they intersect are marked with a "+" instead of an "*"). Therefore, if we simply calculate the sum of the areas, as we did before, 12 + 12 + 9, we will get a too large value (33 instead of 28), because we are calculating the areas with intersection twice.
To get the correct answer, we must subtract the areas where two rectangles intersect: (12 + 12 + 9) - (4 + 1) = 28.
Case 3. Several rectangles have a common intersection at once.

Рассмотрим прямоугольники (0,3,4,0), (2,5,5,1) и (3,3,0,6)
    * * *
    * * *     
* * + x + *      
* * + x + *   
* * * + * *

Now the three rectangles overlap at the points marked with the "x" symbol (as before, the "+" sign where only two rectangles overlap). The sum of the areas of all three triangles is 12 + 12 + 9. Then we must subtract the sum of all the areas where the two rectangles 4 + 3 + 4 intersect (rectangles 1 and 2 intersect in area 4, rectangles 1 and 3 intersect in area 3, and rectangles 2 and 3 intersect in area 4). We got (12 + 12 + 9) - (4 + 3 + 4).
However, by subtracting all the areas where the two rectangles intersect, we subtract the area where the three rectangles intersect (denoted by "x") three times. Therefore, we must add the area of ​​the intersection of the three rectangles to get the correct result. So the total area covered by the rectangles is:
The general rule is actually quite simple. If S1 is the sum of the areas of all rectangles, S2 is the sum of all areas where two rectangles intersect, S3 is the sum of all areas where three rectangles intersect, S4 is the sum of all areas where four rectangles intersect, and so on, the value of the total area is :
This is known in mathematics as the inclusion-exclusion principle , because you alternate between including and excluding areas.
The values ​​in our example correspond to:

S1 = 12 + 12 + 9 
    S2 = 4 + 3 + 4  
    S3 = 2

An example of a calculation using recursion

def bounding_box(rects):
    return (min(r[0] for r in rects),
            max(r[1] for r in rects),
            max(r[2] for r in rects),
            min(r[3] for r in rects))


def area(rect):
    a, b, c, d = rect
    return (c - a) * (b - d)


def clip(bb, rects):
    if not rects:
        return []

    (x1, y1, x2, y2) = rects[0]
    rs = rects[1:]
    (a1, b1, a2, b2) = bb

    if a1 == a2 or b1 == b2:
        return []

    if a1 >= x2 or a2 <= x1 or y1 <= b2 or y2 >= b1:
        return clip(bb, rs)

    result = [(max(a1, x1), min(b1, y1), min(a2, x2), max(b2, y2))]
    return result + clip(bb, rs)


def cover(bb, rects):

    if not rects:
        return 0
    rc = rects[0]
    rs = rects[1:]

    (a1, b1, a2, b2) = bb
    (x1, y1, x2, y2) = rc

    top = (a1, b1, a2, y1)
    bottom = (a1, y2, a2, b2)
    left = (a1, y1, x1, y2)
    right = (x2, y1, a2, y2)

    sum_area = sum(cover(x, clip(x, rs)) for x in [top, bottom, left, right])
    return area(rc) + sum_area


def main():
    width_canvas = 10
    height_canvas = 10

    rect1 = (0, 3, 4, 0)
    rect2 = (2, 5, 5, 1)
    rect3 = (3, 3, 6, 0)
    rs = [rect1, rect2, rect3]

    painted_area = cover(bounding_box(rs), rs)
    canvas_area = width_canvas * height_canvas
    unpainted_area = canvas_area - painted_area

    print("Canvas area:", canvas_area)
    print("Painted area:", painted_area)
    print("Unpainted area:", unpainted_area)


if __name__ == '__main__':
    main()

Code on GitHub Gist
Code on GitHub with tests

Answer 3

rewrite in java and don't worry. Python is rarely used for olympiads because it is slow for this business. The choice of the olympiad is C#, java, C++