fork download 
  1. from bisect import bisect_left
  2. import sys
  3.  
  4. def find_starvation(priorities):
  5.     n = len(priorities)
  6.     if n == 0:
  7.         return []
  8.  
  9.     vals = sorted(set(priorities))
  10.     m = len(vals)
  11.     rank = lambda x: bisect_left(vals, x) + 1
  12.  
  13.     bit = [-1] * (m + 1)
  14.  
  15.     def bit_update(idx, val):
  16.         while idx <= m:
  17.             if val > bit[idx]:
  18.                 bit[idx] = val
  19.             idx += idx & -idx
  20.  
  21.     def bit_query(idx):
  22.         res = -1
  23.         while idx > 0:
  24.             if bit[idx] > res:
  25.                 res = bit[idx]
  26.             idx -= idx & -idx
  27.         return res
  28.  
  29.     ans = [0] * n
  30.     for i in range(n - 1, -1, -1):
  31.         r = rank(priorities[i])
  32.         if r > 1:
  33.             j = bit_query(r - 1)
  34.             if j != -1:
  35.                 ans[i] = j - i
  36.         bit_update(r, i)
  37.     return ans
  38.  
  39. if __name__ == "__main__":
  40.     data = sys.stdin.read().strip().split()
  41.     if not data:
  42.         demo = [6, 10, 9, 7]
  43.         print(*find_starvation(demo))
  44.     else:
  45.         it = iter(data)
  46.         n = int(next(it))
  47.         pri = [int(next(it)) for _ in range(n)]
  48.         print(*find_starvation(pri))
  49.  
Success #stdin #stdout 0.14s 14040KB
comments (?)
stdin 
7 8 2 11 4 9 4 7
stdout 
6 0 4 0 2 0 0
https://ideone.com/h10zss
language:
Python 3 (python  3.12)
created:
4 days ago
visibility:
public

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!