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