fork download
copy 
  1. def insert(tree,levels,n):
  2.         for i in xrange(levels):
  3.                 tree[i][n] += 1
  4.                 n /= 2
  5. def delete(tree,levels,n):
  6.         for i in xrange(levels):
  7.                 tree[i][n] -= 1
  8.                 n /= 2
  9.  
  10. def kthElem(tree,levels,k):
  11.         a = 0
  12.         for b in reversed(xrange(levels)):
  13.                 a *= 2
  14.                 if tree[b][a] < k:
  15.                         k -= tree[b][a]
  16.                         a += 1
  17.         return a
  18.  
  19. def main():
  20.         seed,mul,add,N,K = map(int, "47 5621 1 125000 1700".split())
  21.         levels = 17
  22.         tree = [[0] * 65536 for _ in xrange(levels)]
  23.         temps = [0] * N
  24.         temps[0] = seed
  25.         for i in xrange(1,N):
  26.                 temps[i] = (temps[i-1]*mul + add) % 65536
  27.         result = 0
  28.         for i in xrange(N):
  29.                 insert(tree,levels,temps[i])
  30.                 if (i >= K):
  31.                         delete(tree,levels,temps[i-K])              
  32.                 if (i >= K-1):
  33.                         result += kthElem(tree,levels,((K+1)/2))
  34.  
  35.         print result
  36.  
  37. # default input
  38. # 47 5621 1 125000 1700
  39. # output
  40. # 4040137193
  41.  
  42. import cProfile
  43. cProfile.run("main()")
Success #stdin #stdout 2.37s 10160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4040137193
         371606 function calls in 2.339 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.007    0.007    2.339    2.339 <string>:1(<module>)
   125000    0.699    0.000    0.699    0.000 prog.py:1(insert)
   123301    0.646    0.000    0.646    0.000 prog.py:10(kthElem)
        1    0.352    0.352    2.332    2.332 prog.py:19(main)
   123300    0.636    0.000    0.636    0.000 prog.py:5(delete)
        1    0.000    0.000    0.000    0.000 {map}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 {method 'split' of 'str' objects}
https://ideone.com/gIkevX
language:
Python (cpython 2.7.16)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!