fedor-resh

Untitled

Mar 11th, 2023
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.65 KB | None | 0 0
  1. def bin_search(arr, x):
  2.     l, r = -1, len(arr)
  3.     while r - l > 1:
  4.         m = (l + r) // 2
  5.         if arr[m] > x:
  6.             r = m
  7.         else:
  8.             l = m
  9.     return r
  10. default = (0, 10000) # summ, price
  11. def f(x, y):
  12.     xs, xp = x
  13.     ys, yp = y
  14.     if xs + ys - yp  > xs - xp:
  15.         return xs + ys, yp
  16.     else:
  17.         return x
  18. def update(tree, ind, value):
  19.     if ind < 1: return
  20.     tree[ind] = value
  21.     if ind % 2 == 0:
  22.         update(tree, ind // 2, f(value, tree[ind + 1]))
  23.     else:
  24.         update(tree, ind // 2, f(tree[ind - 1], value))
  25. def init(l):
  26.     from math import log2, ceil
  27.     size = 2 ** ceil(log2(l))
  28.     tree = [default] * (size * 2)
  29.     return tree
  30.  
  31. attack_count, shield_count, monsters_count = map(int, input().split())
  32. attack = [list(map(int, input().split())) for _ in range(attack_count)]
  33. shield = [list(map(int, input().split())) for _ in range(shield_count)]
  34. monsters = [list(map(int, input().split())) for _ in range(monsters_count)]  # shield, attack, reward
  35. MAX = 0
  36. monsters.sort()
  37. cur_monsters = []
  38. m = 0
  39. tree = init(len(shield))
  40. tsize = len(tree) // 2
  41. shield.sort()
  42. shieldes = [s[0] for s in shield]
  43. for i in range(len(shield)):
  44.     update(tree, tsize + i, (0, shield[i][1]))
  45. for a, pr in attack:
  46.     while m < len(monsters) and a > monsters[m][0]:
  47.         monster = monsters[m]
  48.         ind = bin_search(shieldes, monster[1])
  49.         if ind < len(shield):
  50.             update(tree, tsize+ind, (tree[tsize + ind][0] + monster[2], shield[ind][1]))
  51.         m += 1
  52.         print(f'{tree=} {a=} {pr=} {monster=}')
  53.     m_def = tree[1][0] - tree[1][1]
  54.     MAX = max(m_def - pr, MAX)
  55. print(MAX)
  56.  
Advertisement
Add Comment
Please, Sign In to add comment