Magician and Pigs (Easy Version) (Codeforces 1774F1)
Tags: Implement, data structures

This is the easy version of the problem. The only difference between the two versions is the constraint on $$$n$$$ and $$$x$$$. You can make hacks only if both versions of the problem are solved.Little09 has been interested in magic for a long time, and it's so lucky that he meets a magician! The magician will perform $$$n$$$ operations, each of them is one of the following three: $$$1\ x$$$: Create a pig with $$$x$$$ Health Points.  $$$2\ x$$$: Reduce the Health Point of all living pigs by $$$x$$$.  $$$3$$$: Repeat all previous operations. Formally, assuming that this is the $$$i$$$-th operation in the operation sequence, perform the first $$$i-1$$$ operations (including "Repeat" operations involved) in turn.A pig will die when its Health Point is less than or equal to $$$0$$$. Little09 wants to know how many living pigs there are after all the operations. Please, print the answer modulo $$$998\,244\,353$$$.

Input: The first line contains a single integer $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$)  — the number of operations.Each of the following $$$n$$$ lines contains an operation given in the form described in the problem statement. It's guaranteed that $$$1\leq x\leq 2\cdot 10^5$$$ in operations of the first two types.

Output: Print a single integer  — the number of living pigs after all the operations, modulo $$$998\,244\,353$$$.

Note: In the first example, the operations are equivalent to repeating four times: create a pig with $$$8$$$ Health Points and then reduce the Health Points of all living pigs by $$$3$$$. It is easy to find that there are two living pigs in the end with $$$2$$$ and $$$5$$$ Health Points.

Sample Inputs:
4
1 8
2 3
3
3

6
1 5
1 6
2 2
3
1 4
3

12
2 1
1 15
1 9
3
1 12
2 2
1 13
3
2 1
1 9
1 8
3

Sample Outputs:
2

5

17

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]
import bisect

class BIT_SortedSet:

    def __init__(self, A, compress=True, sort_flag=False):
        self.compress = compress
        self.N = len(A)
        self.log = 0
        while self.N >= 1 << self.log + 1:
            self.log += 1
        if compress:
            if sort_flag:
                self.A = A
            else:
                self.A = sorted(A)
            self.index_dic = {}
            for i in range(len(A)):
                self.index_dic[self.A[i]] = i
        else:
            self.A = A
        self.BIT = [0] * (self.N + 5)
        self.size = 0
        self.cnt = [0] * self.N

    def BIT_add(self, i, x):
        idx = i + 1
        while idx < self.N + 1:
            self.BIT[idx] += x
            idx += idx & -idx

    def BIT_query(self, i):
        res = 0
        idx = i + 1
        while idx:
            res += self.BIT[idx]
            idx -= idx & -idx
        return res

    def BIT_lower_left(self, w):
        if w <= 0 or w > self.size:
            return None
        x = 0
        k = 1 << self.log
        while k > 0:
            if x + k < self.N and self.BIT[x + k] < w:
                w -= self.BIT[x + k]
                x += k
            k //= 2
        return x

    def __contains__(self, x):
        if self.compress:
            x = self.index_dic[x]
        return self.cnt[x] >= 1

    def __len__(self):
        return self.size

    def add(self, x):
        if self.compress:
            x = self.index_dic[x]
        if self.cnt[x] == 1:
            return False
        self.BIT_add(x, 1)
        self.size += 1
        self.cnt[x] += 1
        return True

    def discard(self, x):
        if self.compress:
            x = self.index_dic[x]
        if self.cnt[x] > 0:
            self.BIT_add(x, -1)
            self.size -= 1
            self.cnt[x] -= 1
            return True
        return False

    def find_kth_val(self, k):
        res = self.BIT_lower_left(k + 1)
        if res == None:
            return None
        if self.compress:
            res = self.A[res]
        return res

    def __getitem__(self, x):
        if x < 0:
            x += self.size
        if x < 0 or x >= self.size:
            raise IndexError
        return self.find_kth_val(x)

    def index_right(self, x):
        if self.N == 0:
            return 0
        if x < self.A[0]:
            return 0
        if self.compress:
            y = bisect.bisect_right(self.A, x) - 1
        else:
            y = min(x, self.N - 1)
        return self.BIT_query(y)

    def index(self, x):
        if self.N == 0:
            return 0
        if x <= self.A[0]:
            return 0
        if self.compress:
            y = bisect.bisect_right(self.A, x) - 1
        else:
            y = x
        if y >= self.N:
            y = self.N - 1
        elif self.A[y] == x:
            y -= 1
        return self.BIT_query(y)

    def gt(self, x):
        return self.find_kth_val(self.index_right(x))

    def ge(self, x):
        return self.find_kth_val(self.index(x))

    def lt(self, x):
        return self.find_kth_val(self.index(x) - 1)

    def le(self, x):
        return self.find_kth_val(self.index_right(x) - 1)

    def __str__(self):
        return '{' + ', '.join(map(str, [self.find_kth_val(i) for i in range(self.size)])) + '}'
m = 2 * 10 ** 5 + 10
n = int(input())
query = []
cnt = 0
damage = [0]
d = 0
for _ in range(n):
    q = list(map(int, input().split()))
    if q[0] == 3:
        q += [-1]
    if q[0] == 2:
        d += q[1]
    if q[0] == 3:
        d *= 2
    d = min(d, m)
    query.append(q)
    damage.append(d)
S = BIT_SortedSet(list(range(m)))
S.add(0)
mod = 998244353
res = 1
ans = 0
base = 0
now = [0]
for i in range(n - 1, -1, -1):
    (t, x) = query[i]
    if t == 3:
        d = damage[i]
        if d > 2 * 10 ** 5:
            continue
        if d == 0:
            res *= 2
            res %= mod
            continue
        for i in now.copy():
            if i + d < m:
                now.append(i + d)
                S.add(i + d)
    if t == 2:
        base += x
    if t == 1:
        ans += res * S.index(x - base)
        ans %= mod
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
MOD = 998244353
INV2 = MOD // 2 + 1
P2 = [pow(2, i, MOD) for i in range(31)]
X = 10 ** 9
s2 = 0
s3 = 0
s = []
ipt = []
(n,) = map(int, input().strip().split())
for _ in range(n):
    i = list(map(int, input().strip().split()))
    op = i[0]
    if op == 1:
        ipt.append(i[1])
    elif op == 2:
        s2 += i[1]
        s3 += i[1]
        ipt.append(-i[1])
    elif op == 3 and s3 < X:
        s.append(s3)
        s3 *= 2
        ipt.append(0)
ans = 0
s.append(X + 1)
l = 0
l0 = 0
while l0 < len(s) and s[l0] == 0:
    l0 += 1
tl = l0
p2l0 = pow(2, l0, MOD)
for i in ipt:
    if i == 0:
        if l < l0:
            p2l0 = p2l0 * INV2 % MOD
        l += 1
        tl = max(l, l0)
    elif i < 0:
        s2 += i
    elif i > s2:
        t = 0
        i -= s2
        r = len(s) - 1
        while r > tl and s[r] >= i:
            r -= 1
            if s[r] < i:
                t = (t + P2[r - tl]) % MOD
                i -= s[r]
        t += P2[r - tl]
        ans = (ans + t * p2l0) % MOD
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
MOD = 998244353
INV2 = MOD // 2 + 1
P2 = [pow(2, i, MOD) for i in range(31)]
X = 10 ** 9
s2 = 0
s3 = 0
s = []
ipt = []
(n,) = map(int, input().strip().split())
for _ in range(n):
    i = list(map(int, input().strip().split()))
    op = i[0]
    if op == 1:
        ipt.append(i[1])
    elif op == 2:
        s2 += i[1]
        s3 += i[1]
        ipt.append(-i[1])
    elif op == 3 and s3 < X:
        s.append(s3)
        s3 *= 2
        ipt.append(0)
ans = 0
s.append(X + 1)
l = 0
l0 = 0
while l0 < len(s) and s[l0] == 0:
    l0 += 1
tl = l0
p2l0 = pow(2, l0, MOD)
for i in ipt:
    if i == 0:
        if l < l0:
            p2l0 = p2l0 * INV2 % MOD
        l += 1
        tl = max(l, l0)
    elif i < 0:
        s2 += i
    elif i > s2:
        t = 0
        i -= s2
        r = len(s) - 1
        while r > tl and s[r] >= i:
            r -= 1
            if s[r] < i:
                t = (t + P2[r - tl]) % MOD
                i -= s[r]
        t = (t + P2[r - tl]) % MOD
        ans = (ans + t * p2l0) % MOD
print(ans)