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.
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

Exemplul 2

Intare

30

5

10

25

5

20

15

Iesire

30

30

30

25

25

Rezolvare

#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()

Explicatie

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