Vizualizare sursă pentru „4054 - Seg Max”

== Cerința ==
Vom considera un segment pe axa Ox care începe la poziția 0 și se termină la poziția L.
<br>
Se vor insera pe rând N puncte pe axă, iar după fiecare punct inserat se va afișa lungimea celui mai lung segment delimitat de două puncte (inclusiv 0 și L).
== Date de intrare ==
Programul citește de la tastatură numerele L și N, iar apoi N numere naturlae, reprezentând punctele care urmează să fie inserate.
== Date de ieșire == 
Programul va afișa pe ecran N linii, a i-a linie reprezentând lungimea celui mai lung segment delimitat de două puncte, după inserarea celui de al i-lea punct.
== Restricții și precizări ==
*1 ≤ N ≤ 100 000
*1 ≤ L ≤ 10**18
*Fiecare punct inserat se află în intervalul (0, L)
*Punctele inserate sunt distincte.
*Punctele 0 și L se consideră inserate de la început.
*În cadrul acestei probleme, vom defini lungimea unui segment ca fiind numărul de puncte cu coordonate numere naturale care se află pe segmentul dat.
== Exemplul 1 ==
; Intrare
: 20 4
: 6
: 11
: 15
: 4
; Ieșire
: 15
: 10
: 7
: 6
<br>
== Exemplul 2 ==
; Intare
: 30
: 5
: 10
: 25
: 5
: 20
: 15
; Iesire
: 30
: 30
: 30
: 25
: 25
<br>
== Rezolvare == 
<syntaxhighlight lang="python" line>
#4054 - Seg Max
def check_restrictions(L, N, points):
    if not (1 <= N <= 100000 and 1 <= L <= 10**18):
        return False

    if len(points) != N:
        return False

    if not all(0 < point < L for point in points):
        return False

    return True


def main():
    # Citirea datelor de intrare
    L = int(input())
    N = int(input())
    points = [int(input()) for _ in range(N)]

    # Verificarea restricțiilor
    if not check_restrictions(L, N, points):
        print("false")
        return

    # Inițializare variabile
    sorted_points = [0, L]  # Punctele sortate, începând cu 0 și L
    lengths = [L]  # Lungimile segmentelor după fiecare inserare

    # Procesarea inserărilor
    for point in points:
        # Adăugăm noul punct în ordine
        sorted_points.append(point)
        sorted_points.sort()

        # Recalculăm lungimile segmentelor
        lengths.append(max(sorted_points[i + 1] - sorted_points[i] for i in range(len(sorted_points) - 1)))

    # Afișarea rezultatelor
    for length in lengths[1:]:
        print(length)

if __name__ == "__main__":
    main()

</syntaxhighlight>

== Explicatie ==
Segmentele de lungimi maxime sunt [6, 20], [11, 20], [0, 6], respectiv [15, 20].