4144 - Graffiti

Cerința

RAU-Gigel și-a descoperit o nouă pasiune: graffiti-ul. El simte o nevoie din ce în ce mai puternică de a-și manifesta spiritul artistic, de a exersa, de a explora, și de a încerca noi și noi tehnici … și pentru asta are nevoie de spațiu.

Făcând o incursiune prin cartier, RAU-Gigel descoperă un depou părăsit împrejmuit de un gard format din plăci de beton de lățimi și înălțimi diferite, dispuse în linie continuă. „O pânză imaculată” se gândește el. Și începe să măsoare plăcile de beton, una câte una, cu gândul ca, odată ajuns acasă, să schițeze următoarea sa creație artistică.

El vrea să aleagă câteva plăci de beton alăturate și pe dreptunghiul maximal delimitat de acestea, să își făurească creația. Care este suprafața maximă de desenare ? Ajutați-l pe RAU-Gigel să facă mai multe simulări.

Gardul format din plăci de beton, numerotate de la 1 la 5, de dimensiuni (lățime X înălțime): 4 X 8, 5 X 4, 7 X 2, 3 X 3, 8 X 10 unități de mărime. Prin interogări repetate de forma (x, y), RAU-Gigel vrea să afle cât de mare poate fi suprafața de desenare în formă dreptunghiulară ce va acoperi plăcile de beton alipite: x, x+1, ... , y.

De exemplu, la interogarea (2, 4), desenul va avea lățimea 5 + 7 + 3 = 15, și înălțimea minim (4, 2, 3) = 2, deci suprafața de desenare va fi de mărime 30. Se va folosi peste tot aceeași unitate de mărime.

Date de intrare

Fișierul de intrare graffitiin.txt conține pe prima linie numărul natural N reprezentând numărul de plăci de beton, indexate de la 1 la N, apoi N linii care conțin perechi de forma L H, separate printr-un spațiu, reprezentând lățimea și înălțimea fiecărei plăci de beton. Urmează apoi un rând cu numărul natural Q ce reprezintă numărul de interogări, urmat de Q linii ce conțin interogările: perechi de forma x y, cu x ≤ y, separate printr-un spațiu.

Date de ieșire

Fișierul de ieșire graffitiout.txt va conține răspunsurile la interogări, în ordinea solicitării, câte unul pe linie.

Restricții și precizări

• 1 ⩽ N, Q, L, H ⩽ 100.000

Exemplul 1

Intrare

graffitiin.txt

5

4 8

5 4

7 2

3 3

8 10

2

2 4

4 5

Ieșire

Datele de intrare corespund restricțiilor impuse

graffitiout.txt

30

33

Explicație

Avem 5 plăci de beton cu dimensiunile 4 X 8, 5 X 4, 7 X 2, 3 X 3, 8 X 10 și 2 interogări.

La interogarea (2, 4), suprafața desenată va avea lățimea 5 + 7 + 3 = 15, și înălțimea minim (4, 2, 3) = 2, deci suprafața 30.

La interogarea (4, 5), suprafața desenată va avea lățimea 3 + 8 = 11, iar înălțimea sa va fi 3, deci suprafața 33.

Exemplul 2

Intrare

graffitiin.txt

5

4 8

5 4

7 2

3 3

8 10

100001

2 4

4 5

Ieșire

Datele de intrare NU corespund restricțiilor impuse

Rezolvare

#4144 - Graffiti

def validare_input(n, q, placi):
    if not (1 <= n <= 100000 and 1 <= q <= 100000):
        return False
    if len(placi) != n:
        return False
    for L, H in placi:
        if not (1 <= L <= 100000 and 1 <= H <= 100000):
            return False
    return True


def calcul_suprafata_desen(placi, interogari):
    suprafete_desen = []
    for interogare in interogari:
        x, y = interogare
        latime = sum(placi[i][0] for i in range(x - 1, y))
        inaltime = min(placi[i][1] for i in range(x - 1, y))
        suprafete_desen.append(latime * inaltime)
    return suprafete_desen


def main():
    with open("graffitiin.txt", "r") as fisier:
        n = int(fisier.readline())
        placi = [tuple(map(int, fisier.readline().split())) for _ in range(n)]
        q = int(fisier.readline())
        interogari = [tuple(map(int, fisier.readline().split())) for _ in range(q)]

    if validare_input(n, q, placi):
        print("Datele de intrare corespund restricțiilor impuse")
    else:
        print("Datele de intrare NU corespund restricțiilor impuse")
        exit(0)

    suprafete_desen = calcul_suprafata_desen(placi, interogari)

    with open("graffitiout.txt", "w") as fisier:
        for suprafata in suprafete_desen:
            fisier.write(str(suprafata) + "\n")


if __name__ == "__main__":
    main()