fork download
  1. import random
  2. import heapq
  3.  
  4.  
  5. heap = []
  6. subseqs = {}
  7. prevElem = []
  8. bestL = 0
  9.  
  10.  
  11. def merge(x, p, d):
  12. length1 = subseqs[d][1][p][0]
  13. length2 = subseqs[d][0][x][0]
  14. length = length1 + 1 + length2
  15. begin = subseqs[d][1][p][1]
  16. end = subseqs[d][0][x][1]
  17. del subseqs[d][0][begin]
  18. del subseqs[d][1][end]
  19. del subseqs[d][0][x]
  20. del subseqs[d][1][p]
  21. subseqs[d][0][begin] = (length, end)
  22. subseqs[d][1][end] = (length, begin)
  23.  
  24.  
  25. def growLeft(x, p, d):
  26. length = 1 + subseqs[d][0][x][0]
  27. end = subseqs[d][0][x][1]
  28. del subseqs[d][1][end]
  29. del subseqs[d][0][x]
  30. subseqs[d][0][p] = (length, end)
  31. subseqs[d][1][end] = (length, p)
  32.  
  33.  
  34. def growRight(x, p, d):
  35. length = subseqs[d][1][p][0] + 1
  36. begin = subseqs[d][1][p][1]
  37. del subseqs[d][0][begin]
  38. del subseqs[d][1][p]
  39. subseqs[d][0][begin] = (length, x)
  40. subseqs[d][1][x] = (length, begin)
  41.  
  42.  
  43. def insert(x, p, d):
  44. subseqs[d][0][p] = (1, x)
  45. subseqs[d][1][x] = (1, p)
  46.  
  47.  
  48. def update(x, p, d):
  49. if d not in subseqs:
  50. heapq.heappush(heap, d)
  51. subseqs[d] = ({},{})
  52.  
  53. if x in subseqs[d][0]:
  54. if p in subseqs[d][1]:
  55. merge(x, p, d)
  56. else:
  57. growLeft(x, p, d)
  58. else:
  59. if p in subseqs[d][1]:
  60. growRight(x, p, d)
  61. else:
  62. insert(x, p, d)
  63.  
  64.  
  65. def init(src):
  66. prevElem.insert(0, -1)
  67. for i in range(1, len(src)):
  68. prevElem.insert(i, i-1)
  69. d = src[i] - src[i-1]
  70.  
  71. update(i, i-1, d)
  72.  
  73.  
  74. def chooseTheBest(d):
  75. global bestL
  76. l = max(list(zip(*subseqs[d][0].values()))[0])
  77. if l > bestL:
  78. bestL = l
  79.  
  80.  
  81. def updateIndexes(src, d):
  82. for end in subseqs[d][1].keys():
  83. l = subseqs[d][1][end][0]
  84. i = end
  85.  
  86. for n in range(l):
  87. link = prevElem[i]
  88.  
  89. if link != 0:
  90. prevElem[i] -= 1
  91. d2 = src[i] - src[prevElem[i]]
  92. update(i, prevElem[i], d2)
  93. i = link
  94.  
  95.  
  96. def findLESS(src):
  97. global bestL
  98. init(src)
  99.  
  100. while len(heap) > 0:
  101. #print(subseqs)
  102. d = heapq.heappop(heap)
  103. chooseTheBest(d)
  104. updateIndexes(src, d)
  105. del subseqs[d]
  106.  
  107. return bestL
  108.  
  109.  
  110. a = [random.randint(0,20000) for r in range(20000)]
  111. s = list(set(a))
  112.  
  113. print(findLESS(s) + 1)
  114.  
Not running #stdin #stdout 0s 0KB
stdin
Standard input is empty
stdout
Standard output is empty