1639 - Secvente 3

Considerăm şirul de numere naturale nenule distincte . Notăm cu  lungimea maximă a unei secvențe de elemente cu valori consecutive care se poate obţine prin ordonarea crescătoare a primelor i elemente din şirul dat. De exemplu, pentru șirul 7, 2, 3, 8, 20, 4, 10, 9 avem: .

Cerința

Să se determine .

Date de intrare

Fişierul input.txt conţine pe prima linie numărul natural N. Pe fiecare din următoarele N linii se găseşte câte un număr natural, deci pe linia i+1 se va afla elementul , pentru i=1...N.

Date de ieșire

Fişierul output.txt conţine exact N linii. Pe linia i (i = 1...N) se va afișa valoarea .

Restricții și precizări

• 3 ≤ N ≤ 200.000

Exemplul 1

input.txt:

8

7

3

2

8

20

4

10

9

output.txt:

1

1

2

2

2

3

3

4

Explicație:

L1 Șirul: 7. Lungime maximă 1.

L2 Șirul: 7, 3. Lungime maximă 1.

L3 Șirul: 7, 3, 2. Şirul sortat este 2, 3, 7. Lungimea maximă este 2 (dată de secvenţa 2, 3).

L4 Șirul: 7, 3, 2, 8. Lungime maximă 2 (dată de 2, 3)

L5 Șirul: 7, 3, 2, 8, 20. Lungime maximă 2 (dată de 2, 3).

L6 Șirul: 7, 3, 2, 8, 20, 4. Şirul sortat este 2, 3, 4, 7, 8, 20. Lungimea maximă este 3 (dată de secvenţa 2, 3, 4).

L7 Șirul: 7, 3, 2, 8, 20, 4, 10. Lungime maximă 3 (dată de 2, 3, 4).

L8 Șirul: 7, 3, 2, 8, 20, 4, 10, 9. Şirul sortat este 2, 3, 4, 7, 8, 9, 10, 20. Lungimea maximă este 4 (dată de secvenţa 7, 8, 9, 10).

Exemplul 2

input.txt:

999999999

7

3

2

8

20

4

10

9

Output:

Input-ul nu convine conditiilor

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verificare(n):

   if not(3<=n<=200000):
       print("Input-ul nu convine conditiilor")
       exit()

infile = "input.txt" outfile = "output.txt" nMax = 200013 vMax = 1000013

vz = [False] * vMax v = [0] * nMax pos = [0] * vMax n = 0

def read():

   global n
   with open(infile, "r") as fin:
       n = int(fin.readline().strip())
       verificare(n)
       for i in range(n):
           v[i + 1] = int(fin.readline().strip())
           assert not vz[v[i + 1]]
           vz[v[i + 1]] = True

def solve():

   global n
   best = 0

   with open(outfile, "w") as fout:
       for i in range(1, n + 1):
           begin, end = v[i], v[i]

           if pos[v[i] - 1]:
               begin = pos[v[i] - 1]
           if pos[v[i] + 1]:
               end = pos[v[i] + 1]

           pos[begin] = end
           pos[end] = begin

           best = max(best, end - begin + 1)
           fout.write(f"{best}\n")

if __name__ == "__main__":

   read()
   solve()

</syntaxhighlight>