Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def bin_search(arr, x):
- l, r = -1, len(arr)
- while r - l > 1:
- m = (l + r) // 2
- if arr[m] > x:
- r = m
- else:
- l = m
- return r
- default = (0, 10000) # summ, price
- def f(x, y):
- xs, xp = x
- ys, yp = y
- if xs + ys - yp > xs - xp:
- return xs + ys, yp
- else:
- return x
- def update(tree, ind, value):
- if ind < 1: return
- tree[ind] = value
- if ind % 2 == 0:
- update(tree, ind // 2, f(value, tree[ind + 1]))
- else:
- update(tree, ind // 2, f(tree[ind - 1], value))
- def init(l):
- from math import log2, ceil
- size = 2 ** ceil(log2(l))
- tree = [default] * (size * 2)
- return tree
- attack_count, shield_count, monsters_count = map(int, input().split())
- attack = [list(map(int, input().split())) for _ in range(attack_count)]
- shield = [list(map(int, input().split())) for _ in range(shield_count)]
- monsters = [list(map(int, input().split())) for _ in range(monsters_count)] # shield, attack, reward
- MAX = 0
- monsters.sort()
- cur_monsters = []
- m = 0
- tree = init(len(shield))
- tsize = len(tree) // 2
- shield.sort()
- shieldes = [s[0] for s in shield]
- for i in range(len(shield)):
- update(tree, tsize + i, (0, shield[i][1]))
- for a, pr in attack:
- while m < len(monsters) and a > monsters[m][0]:
- monster = monsters[m]
- ind = bin_search(shieldes, monster[1])
- if ind < len(shield):
- update(tree, tsize+ind, (tree[tsize + ind][0] + monster[2], shield[ind][1]))
- m += 1
- print(f'{tree=} {a=} {pr=} {monster=}')
- m_def = tree[1][0] - tree[1][1]
- MAX = max(m_def - pr, MAX)
- print(MAX)
Advertisement
Add Comment
Please, Sign In to add comment