2510 - vsecvente

Cerința

Considerăm un șir de numere naturale nenule a[1], a[2], …, a[n]. În acest șir o V-secvență este o secvență maximală de forma a[x], a[x+1], …, a[y] cu proprietatea că toate numerele din secvență au valori mai mici sau egale cu V. Este maximală pentru că nu poate fi extinsă spre stânga sau spre dreapta. De exemplu, șirul a = 2, 2, 6, 4, 3, 14, 7, 4, 3, 36 are două 7-secvențe: 2, 2, 6, 4, 3 și 7, 4, 3. De asemenea, șirul are trei 4-secvențe: 2,2; 4,3; 4,3. De notat că 2,6,4,3 nu este 7-secvență, deoarece poate fi extinsă la capătul său stâng cu numărul 2. Pentru un șir de numere dat, trebuie să răspundeți la Q întrebări notate V[1], V[2],…, V[Q]. Pentru fiecare întrebare i, dată prin numărul natural V[i], trebuie să aflați câte V[i]-secvențe sunt în șir.

Date de intrare

Fișierul de intrare vsecvente.in conține pe prima linie numărul natural N. Pe a doua linie, separate prin câte un spațiu, se află cele N elemente ale șirului. Pe a treia linie se află un singur număr natural Q reprezentând numărul de întrebări. Pe a patra linie, se află șirul de Q numere naturale V[1], V[2],…, V[Q], separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire vsecvente.out va conține Q linii. Linia a i-a va conține numărul de V[i]-secvențe aflate în șir.

Exemplu 1

• 1 ≤ toate numerele din fișierul de intrare ≤ 1 100 000
• Pentru teste totalizând 75 puncte, 1 ≤ toate numerele din fișierul de intrare ≤ 550 000

Intrare

10
2 2 6 4 3 14 7 4 3 36
3
7 1 4

Iesire

2
0
3

Rezolvare

def main():
    # Citirea datelor de intrare
    with open('vsecvente.in', 'r') as f:
        data = f.read().splitlines()

    # Prima linie conține numărul N
    N = int(data[0].strip())

    # Asigurăm că 1 ≤ N ≤ 100000
    assert 1 <= N <= 100000, "N trebuie să fie între 1 și 100000"

    # A doua linie conține N elemente ale șirului
    sir = list(map(int, data[1].strip().split()))

    # Verificăm că lungimea șirului este corectă
    assert len(sir) == N, "Lungimea șirului trebuie să fie N"

    # A treia linie conține numărul de întrebări Q
    Q = int(data[2].strip())

    # Asigurăm că 1 ≤ Q ≤ 100000
    assert 1 <= Q <= 100000, "Q trebuie să fie între 1 și 100000"

    # A patra linie conține Q valori pentru interogări
    interogari = list(map(int, data[3].strip().split()))

    # Verificăm că lungimea interogărilor este corectă
    assert len(interogari) == Q, "Numărul interogărilor trebuie să fie Q"

    # Asigurăm că toate elementele din șir sunt între 1 și 1,000,000,000
    for elem in sir:
        assert 1 <= elem <= 1000000000, "Elementele șirului trebuie să fie între 1 și 1,000,000,000"

    # Asigurăm că toate interogările sunt între 1 și 1,000,000,000
    for interogare in interogari:
        assert 1 <= interogare <= 1000000000, "Interogările trebuie să fie între 1 și 1,000,000,000"

    rezultate = []

    # Pentru fiecare interogare, calculăm numărul de secvențe maxime pentru valoarea V
    for V in interogari:
        count = 0
        in_sequence = False
        for num in sir:
            if num <= V:
                if not in_sequence:
                    in_sequence = True
                    count += 1
            else:
                in_sequence = False
        rezultate.append(count)

    # Scrierea rezultatelor în fișierul de ieșire
    with open('vsecvente.out', 'w') as f:
        for rezultat in rezultate:
            f.write(f"{rezultat}\n")

if __name__ == "__main__":
    main()