Spaceship Solitaire (Codeforces 1266E)
Tags: Greedy, data structures

Bob is playing a game of Spaceship Solitaire. The goal of this game is to build a spaceship. In order to do this, he first needs to accumulate enough resources for the construction. There are $$$n$$$ types of resources, numbered $$$1$$$ through $$$n$$$. Bob needs at least $$$a_i$$$ pieces of the $$$i$$$-th resource to build the spaceship. The number $$$a_i$$$ is called the goal for resource $$$i$$$.Each resource takes $$$1$$$ turn to produce and in each turn only one resource can be produced. However, there are certain milestones that speed up production. Every milestone is a triple $$$(s_j, t_j, u_j)$$$, meaning that as soon as Bob has $$$t_j$$$ units of the resource $$$s_j$$$, he receives one unit of the resource $$$u_j$$$ for free, without him needing to spend a turn. It is possible that getting this free resource allows Bob to claim reward for another milestone. This way, he can obtain a large number of resources in a single turn.The game is constructed in such a way that there are never two milestones that have the same $$$s_j$$$ and $$$t_j$$$, that is, the award for reaching $$$t_j$$$ units of resource $$$s_j$$$ is at most one additional resource.A bonus is never awarded for $$$0$$$ of any resource, neither for reaching the goal $$$a_i$$$ nor for going past the goal — formally, for every milestone $$$0 < t_j < a_{s_j}$$$.A bonus for reaching certain amount of a resource can be the resource itself, that is, $$$s_j = u_j$$$.Initially there are no milestones. You are to process $$$q$$$ updates, each of which adds, removes or modifies a milestone. After every update, output the minimum number of turns needed to finish the game, that is, to accumulate at least $$$a_i$$$ of $$$i$$$-th resource for each $$$i \in [1, n]$$$.

Input: The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of types of resources.The second line contains $$$n$$$ space separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$), the $$$i$$$-th of which is the goal for the $$$i$$$-th resource.The third line contains a single integer $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — the number of updates to the game milestones.Then $$$q$$$ lines follow, the $$$j$$$-th of which contains three space separated integers $$$s_j$$$, $$$t_j$$$, $$$u_j$$$ ($$$1 \leq s_j \leq n$$$, $$$1 \leq t_j < a_{s_j}$$$, $$$0 \leq u_j \leq n$$$). For each triple, perform the following actions:   First, if there is already a milestone for obtaining $$$t_j$$$ units of resource $$$s_j$$$, it is removed.  If $$$u_j = 0$$$, no new milestone is added.  If $$$u_j \neq 0$$$, add the following milestone: "For reaching $$$t_j$$$ units of resource $$$s_j$$$, gain one free piece of $$$u_j$$$."  Output the minimum number of turns needed to win the game. 

Output: Output $$$q$$$ lines, each consisting of a single integer, the $$$i$$$-th represents the answer after the $$$i$$$-th update.

Note: After the first update, the optimal strategy is as follows. First produce $$$2$$$ once, which gives a free resource $$$1$$$. Then, produce $$$2$$$ twice and $$$1$$$ once, for a total of four turns.After the second update, the optimal strategy is to produce $$$2$$$ three times — the first two times a single unit of resource $$$1$$$ is also granted.After the third update, the game is won as follows.   First produce $$$2$$$ once. This gives a free unit of $$$1$$$. This gives additional bonus of resource $$$1$$$. After the first turn, the number of resources is thus $$$[2, 1]$$$.  Next, produce resource $$$2$$$ again, which gives another unit of $$$1$$$.  After this, produce one more unit of $$$2$$$. The final count of resources is $$$[3, 3]$$$, and three turns are needed to reach this situation. Notice that we have more of resource $$$1$$$ than its goal, which is of no use.

Sample Inputs:
2
2 3
5
2 1 1
2 2 1
1 1 1
2 1 2
2 2 0

Sample Outputs:
4
3
3
2
3

Solution (Python):
import sys
import math
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
cur = [0] * n
tot = sum(arr)
dic = {}
q = int(input())
for j in range(q):
    (s, t, u) = map(int, input().split())
    if (s, t) in dic:
        v = dic[s, t]
        del dic[s, t]
        if cur[v - 1] <= arr[v - 1]:
            tot += 1
        cur[v - 1] -= 1
    if u > 0:
        dic[s, t] = u
        if cur[u - 1] < arr[u - 1]:
            tot -= 1
        cur[u - 1] += 1
    print(tot)

Solution (Python):
import sys
import math
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
cur = [0] * n
tot = sum(arr)
dic = {}
q = int(input())
for i in range(q):
    (s, t, u) = map(int, input().split())
    if (s, t) in dic:
        v = dic[s, t]
        del dic[s, t]
        if cur[v - 1] <= arr[v - 1]:
            tot += 1
        cur[v - 1] -= 1
    if u > 0:
        dic[s, t] = u
        if cur[u - 1] < arr[u - 1]:
            tot -= 1
        cur[u - 1] += 1
    print(tot)

Solution (Python):
import os, sys
from io import BytesIO, IOBase

def main():
    n = int(input())
    a = [0] + list(map(int, input().split()))
    su = sum(a)
    le = [0] * (n + 1)
    dct = {}
    for _ in range(int(input())):
        (s, t, u) = map(int, input().split())
        x = dct.get((s, t))
        if x:
            le[x] -= 1
            if le[x] < a[x]:
                su += 1
            del dct[s, t]
        if u:
            dct[s, t] = u
            le[u] += 1
            if le[u] <= a[u]:
                su -= 1
        print(su)
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()