Zadanie

Píše sa 31. december 1999. Frajerskí Kóderi Systémov nezískali tender na napísanie programu pre tajnú jadrovú elektráreň na matfyze. Jednalo sa o jeden z najdôležitejších programov – program na ovládanie žiarovky vnútri kontrolnej miestnosti. Len si predstavte tú galibu, keby bola v kontrolnej miestnosti tma. Alebo nebodaj, keby sa žiarovka zapla dvakrát. Brr – určite aj vás striaslo pri tejto myšlienke. Zákazku namiesto vás získal Klub Machrov Skoro-programátorov.

Mišofovi, vtedy ešte mladému a udatnému junákovi, to akosi nedalo. Vkradol sa preto pod rúškom noci do KMS servera a prezrel program, ktorý napísali. Chcel by program otestovať. Najprv však musí po sebe upratať, aby nikto nezistil, že tam lozil. Pomôžte mu zatiaľ napísať program, ktorým by otestoval to čo vytvorili KMS-áci!

Úloha

Na vstupe dostanete rozvrh časov, kedy má byť žiarovka zapnutá. Zistite, či v tomto rozvrhu nastane situácia, kedy by žiarovka mala byť zapnutá viackrát naraz.

Formát vstupu

Na prvom riadku vstupu dostanete dve čísla - \(n\) a \(m\). Číslo \(n\) (\(1 \leq n \leq 10^6\)) udáva dĺžku tmy v sekundách a číslo \(m\) (\(1 \leq m \leq 500\,000\)) je počet intervalov, kedy má byť žiarovka zapnutá. Každý z následujúcich \(m\) riadkov obsahuje dve čísla \(a\) a \(b\) \((0 \leq a < b \leq n)\). Žiarovka by mala byť zapnutá v polootvorenom intervale \([a, b)\), teda od času \(a\) do času \(b - 1\) vrátane.

Formát výstupu

Vypíšte reťazec ANO ak je žiarovka zapnutá v nejakom momente viac ako raz. Inak vypíšte reťazec NIE.

Príklad

Input:

5 3
0 1
1 2
2 3

Output:

NIE

Input:

10 3
3 5
0 2
1 2

Output:

ANO

Problémy v reaktore našťastie nie sú tentokrát také zlé. Niektorým ľudom ale dali trochu zabrať.

Jedným z riešení je skúsiť každý interval so všetkými ostatnými a skontrolovať, či sa prekrývajú. Toto riešenie ale nie je moc efektívne, pretože porovnávame každý interval s každým iným, čo je \(O(n^2)\). Keďže \(n\) môže byť až milión, toto nie je úplne postačujúce na plný počet bodov.

Kľúčovým pozorovaním je, že časových blokov je iba milión. Milión je pre počítač vcelku malé číslo - bežný počítač vie urobiť približne \(10^8\) operácií za sekundu. Pre vyriešenie úlohy na plný počet bodov si teda stačí vytvoriť jedno pole veľkosti \(n\) (najviac milión) a označovať si, v ktorých blokoch už je žiarovka zapnutá. Pokiaľ narazíme na druhé zapnutie žiarovky na nejakom bloku (inými slovami, nájdeme kolíziu), vypíšeme ANO, pokiaľ sme žiadnu kolíziu nenašli, vypíšeme NIE.

Toto riešenie má časovú zložitosť \(O(n)\), keďže na každý blok sa pozrieme jedenkrát. Pamäťovú zložitosť má tiež \(O(n)\), keďže potrebujeme vytvoriť pole veľkosti \(n\). Treba si dávať pozor, aj keď \(n\) môže byť iba milión, nejedná sa o konštantú časovú zložitosť. Toto ‘’umelé’’ obmedzenie \(n\) je iba z dôvodov testovania vašich riešení.

#!/usr/bin/env python3
n, m = map(int, input().split())

bloky = [False] * 10**6
for _ in range(m):
    a, b = map(int, input().split())
    for i in range(a, b):
        if bloky[i] is True:
            print("ANO")
            exit(0)
        else:
            bloky[i] = True

print("NIE")

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.