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