Úloha nám zadala dve množiny intervalov určitých typov a máme zistiť veľkosť prieniku intervalov rovnakého typu.

Naivné riešenie

Úloha je rozdelená do troch sád. Riešenie, ktoré zvládne vyriešiť iba prvú sadu, ani neviem, aké je, keďže najjednoduchšia vec, čo ma vie napadnúť, rieši rovno aj tú druhú.

Toto riešenie je, že si „komplikovaný“ formát intervalov, ktoré sme dostali na vstupe, premeníme na priamočiaru „dekomprimovanú“ reprezentáciu s dvomi poľami A a B dĺžky $N$. Keď už si pamätáme dve polia rovnakej dĺžky, zostane nám iba prejsť cez všetky pozície a skontrolovať, koľko z nich je naozaj v oboch poliach rovnakých.

for i in range(N):
    if A[i] == B[i]:
        odpoved += 1

# alebo aj iné varianty pre nadšencov pythonu
odpoved = len([i for i in range(N) if A[i] == B[i]])
odpoved = sum(a == b for a, b in zip(A, B))

Časová a pamäťová zložitosť bude O(N), keďže si vytvárame dve polia dĺžky $N$ a prechádzame cez ne.

Vzorové riešenie

Predstavme si, že budeme brať suroviny po jednej z oboch koncov poličiek naraz. Niekedy sa nám pošťastí a budeme mať na konci rovnaké suroviny, inokedy budeme mať smolu a budú rôzne. Aj napriek Miškiným poverám ich však odstránime, aby sme mohli pokračovať ďalej.

No ale všimnime si, že keďže suroviny tvoria v poličkách súvislé úseky rovnakého typu, tak či už sa nám pošťastí alebo nie, častokrát bude mať ďalšia dvojica surovín, na ktoré sa pozrieme, rovnaký výsledok. Napríklad sme práve odobrali dvojicu surovín, ktoré boli rovnaké, a vidíme, že suroviny patrili do úsekov, kde v hornej poličke zostáva ešte $1000$ rovnakých surovín a v dolnej $1234$ rovnakých surovín. Tak teraz by sme nemuseli $1000$-krát opakovať to isté. Už od pohľadu vidno, že najbližších $1000$ dvojíc bude rovnakých a vieme si ušetriť strašne veľa roboty. Tak pripočítame $1000$ ku výsledku, zmažeme celý horný úsek a dolný úsek zmenšíme o $1000$, čiže v ňom zostane ešte $234$ surovín.

Toto vieme všeobecne popísať tak, že máme dva zásobníky úsekov pre hornú a dolnú poličku. Nech $m$ je minimum z dĺžok úsekov na vrchu zásobníkov. Potom vieme, že najbližších $m$ dvojíc surovín bude mať rovnaký výsledok, a teda ak sú rovnaké, tak pripočítame $m$ do výsledku a oba úseky zmenšíme o $m$. To má ihneď za následok, že aspoň jeden z týchto úsekov bude prázdny a vieme ho zo zásobníka zmazať. Tento postup vieme opakovať, kým nevyprázdnime oba zásobníky.

V každom kroku odstránime zo zásobníka aspoň jeden prvok, takže počet krokov bude maximálne $X + Y$. Na to, aby toto fungovalo, však musia byť úseky zoradené podľa začiatku. Časová zložitosť je teda $O(X \log X + Y \log Y)$ kvôli triedeniu a pamäťová $O(X + Y)$.

N = int(input())
rows = [sorted(tuple(map(int, input().split())) for _ in range(int(input()))) for _ in range(2)]
rowA, rowB = [[(hi - lo + 1, t) for lo, hi, t in row] for row in rows]

res = 0
while rowA and rowB:
    lA, tA = rowA.pop()
    lB, tB = rowB.pop()
    l = min(lA, lB)
    res += l if tA == tB else 0
    lA, lB = lA - l, lB - l
    if lA:
        rowA.append((lA, tA))
    if lB:
        rowB.append((lB, tB))

print(res)

Keby sme mali úseky už utriedené na vstupe, časová zložitosť by bola iba $O(X + Y)$. Okrem toho si všimnime, že je jedno, či berieme suroviny zľava alebo sprava. Preto, ak by sme mali vstup už utriedený, nemuseli by sme si pamätať druhý zásobník, ale všetko vyhodnocovať zároveň, čo načítavame vstup druhej poličky, čím by sme dosiahli pamäťovú zložitosť $O(X)$.

Zbytočné riešenie

Aj napriek tomu, že vstup nie je utriedený, vieme stále zlepšiť pamäťovú zložitosť na $O(X)$. Zatiaľ čo všetky úseky z prvej poličky máme zapamätané v utriedenom poli, úseky z druhej poličky nám stačí vyhodnocovať počas načítavania. Vždy, keď načítame úsek druhej poličky, vieme binárne vyhľadať prvý príslušný úsek v prvej poličke a potom vykonať horeopísaný postup.

Takto si nikdy nemusíme pamätať druhú poličku, čiže pamäťová zložitosť bude $O(X)$. Navyše si vieme uvedomiť, že pri vykonávaní horeopísaného postupu $Y$-krát dokopy nevykonáme viac ako $O(X + Y)$ krokov. Časová zložitosť je teda $O(X \log X + Y \log X) = O((X + Y) \log X)$ (všimnime si, že máme tentoraz $\log X$ pri $Y$, keďže binárne vyhľadávame v poli dĺžky $X$).

Samozrejme, toto nebolo nutné na získanie plného počtu bodov.