2534 - Bogdan

Bogdan și Ionuț au fost "bff" încă din clasa V, dar acum destinele lor se cam despart…. Pentru a-l consola pe Bogdan, Ionuț i-a făcut o problema cadou. Bogdan nu vrea să-l dezamăgească pe Ionut, așa că vă cere ajutorul pentru a rezolva problema împreuna.

Cerința

Se dă un șir de n elemente, numere naturale. Problema constă în două operații:

1 i val : Elementul de pe poziția i se înlocuiește cu valoarea val. 2 i j : Stabiliți dacă secvența [i,j], din șirul curent, este ordonată crescător.

Date de intrare

Fișierul de intrare bogdanin.txt conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații. Pe a treia linie a fișierului se afla numărul O, care reprezintă numărul de operații. Pe următoarele O linii se vor afla operațiile.

Date de ieșire

Fișierul de ieșire bogdanout.txt va conține răspunsurile pentru operațiile de tipul 2, pe linie nouă fiecare. Dacă răspunsul este afirmativ, se va afișa DA, în caz contrar NU.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• 1 ≤ O ≤ 300.000
• numerele fiecărui șir curent vor fi mai mici decât 2.000.000.000
• Observație importantă : bff = Best Friends Forever

Exemplul 1

bogdanin.txt

6
22 9 2003 14 8 2003
4
2 1 6
1 1 8
2 1 3
2 4 5

bogdanout.txt

Datele de intrare corespund restrictiilor impuse
NU
DA
NU

Exemplul 2

bogdanin.txt

bogdan

bogdanout.txt

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

def validare(nr_n, string,
             nr_o, fisier_out):  # functia de validare a datelor de intrare
    if not (1 <= nr_n <= 100000):
        raise ValueError("n nu este in intervalul [1, 100000]")

    if not (1 <= nr_o <= 300000):
        raise ValueError("O nu este in intervalul [1, 300000]")

    for numar in string:
        if not (numar < 2000000000):  # fiecare numar trebuie sa fie mai mic decat 2.000.000.000
            raise ValueError("Un numar din sir este mai mare sau egal cu 2.000.000.000")

    fisier_out.write("Datele de intrare corespund restrictiilor impuse\n")


def rezolvare(string, exercitii, fisier_out):  # functia de rezolvare
    for operatie in exercitii:
        if operatie[0] == 1:
            string[operatie[1] - 1] = operatie[2]
        elif operatie[0] == 2:
            if string[operatie[1] - 1:operatie[2]] == sorted(string[operatie[1] - 1:operatie[2]]):
                fisier_out.write("DA\n")
            else:
                fisier_out.write("NU\n")


if __name__ == '__main__':
    file_in = open("bogdanin.txt", "r")  # declararea fisierelor
    file_out = open("bogdanout.txt", "w")  # fisierul out trebuie declarat cu optiunea "w" (write)

    try:
        n_str = file_in.readline().strip()  # citirea numarului ca sir de caractere
        try:
            n = int(n_str)  # incercam sa convertim sirul de caractere in numar intreg
        except ValueError:
            file_out.write("Datele de intrare nu corespund restrictiilor impuse\n")
            file_in.close()
            file_out.close()
            exit(0)  # iesim din program daca conversia esueaza

        sir = list(map(int, file_in.readline().split()))

        o = int(file_in.readline())
        operatii = [list(map(int, file_in.readline().split())) for _ in range(o)]

        validare(n, sir, o, file_out)  # apelul functiei de validare
        rezolvare(sir, operatii, file_out)  # apelul functiei de rezolvare

    except ValueError as ve:
        file_out.write(str(ve))
    except IndexError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")

    file_in.close()
    file_out.close()