Berserk Monsters (Codeforces 1922D)
Tags: Math, dsu

Monocarp is playing a computer game (yet again). Guess what is he doing? That's right, killing monsters.There are $$$n$$$ monsters in a row, numbered from $$$1$$$ to $$$n$$$. The $$$i$$$-th monster has two parameters: attack value equal to $$$a_i$$$ and defense value equal to $$$d_i$$$. In order to kill these monsters, Monocarp put a berserk spell on them, so they're attacking each other instead of Monocarp's character.The fight consists of $$$n$$$ rounds. Every round, the following happens:  first, every alive monster $$$i$$$ deals $$$a_i$$$ damage to the closest alive monster to the left (if it exists) and the closest alive monster to the right (if it exists);  then, every alive monster $$$j$$$ which received more than $$$d_j$$$ damage during this round dies. I. e. the $$$j$$$-th monster dies if and only if its defense value $$$d_j$$$ is strictly less than the total damage it received this round. For each round, calculate the number of monsters that will die during that round.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.Each test case consists of three lines:  the first line contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$);  the second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$);  the third line contains $$$n$$$ integers $$$d_1, d_2, \dots, d_n$$$ ($$$1 \le d_i \le 10^9$$$). Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output: For each test case, print $$$n$$$ integers. The $$$i$$$-th integer should be equal to the number of monsters that die during the $$$i$$$-th round.

Note: Explanation for the first test case of the example:During the first round, the following happens:  the monster $$$1$$$ deals $$$3$$$ damage to the monster $$$2$$$;  the monster $$$2$$$ deals $$$4$$$ damage to the monster $$$1$$$ and the monster $$$3$$$;  the monster $$$3$$$ deals $$$7$$$ damage to the monster $$$2$$$ and the monster $$$4$$$;  the monster $$$4$$$ deals $$$5$$$ damage to the monster $$$3$$$ and the monster $$$5$$$;  the monster $$$5$$$ deals $$$10$$$ damage to the monster $$$4$$$;  the monster $$$1$$$ does not die, since it received $$$4$$$ damage and its defense is $$$4$$$;  the monster $$$2$$$ dies, since it received $$$10$$$ damage and its defense is $$$9$$$;  the monster $$$3$$$ dies, since it received $$$9$$$ damage and its defense is $$$1$$$;  the monster $$$4$$$ does not die, since it received $$$17$$$ damage and its defense is $$$18$$$;  the monster $$$5$$$ dies, since it received $$$5$$$ damage and its defense is $$$1$$$. After the first round, the monsters $$$1$$$ and $$$4$$$ stay alive.During the second round, the following happens:  the monster $$$1$$$ deals $$$3$$$ damage to the monster $$$4$$$;  the monster $$$4$$$ deals $$$5$$$ damage to the monster $$$1$$$;  the monster $$$1$$$ dies, since it received $$$5$$$ damage and its defense is $$$4$$$;  the monster $$$4$$$ does not die, since it received $$$3$$$ damage and its defense is $$$18$$$. During the next three rounds, only the $$$4$$$-th monster is alive, so nothing happens.

Sample Inputs:
3
5
3 4 7 5 10
4 9 1 18 1
2
2 1
1 3
4
1 1 2 4
3 3 4 2

Sample Outputs:
3 1 0 0 0 
0 0 
1 1 1 0

Solution (Python):
T = int(input())

def solve():
    n = int(input())
    a = [0] + list(map(int, input().split())) + [0]
    d = [0] + list(map(int, input().split())) + [0]
    l = [0] + [i - 1 for i in range(1, n + 1)] + [n]
    r = [1] + [i + 1 for i in range(1, n + 1)] + [0]
    v = [0] * (n + 2)
    v[0] = v[n + 1] = 1
    q = []
    ans = [0] * n
    for i in range(1, n + 1):
        if a[l[i]] + a[r[i]] > d[i]:
            q.append(i)
    cur = 0
    while q:
        ans[cur] = len(q)
        for i in q:
            r[l[i]] = r[i]
            l[r[i]] = l[i]
            v[i] = 1
        nx = []
        for i in q:
            if not v[l[i]]:
                t = l[i]
                if a[l[t]] + a[r[t]] > d[t]:
                    nx.append(t)
                    v[t] = 1
            if not v[r[i]]:
                t = r[i]
                if a[l[t]] + a[r[t]] > d[t]:
                    nx.append(t)
                    v[t] = 1
        q = nx
        cur += 1
    print(*ans)
for _ in range(T):
    solve()

Solution (Python):
T = int(input())

def solve():
    n = int(input())
    a = [0] + list(map(int, input().split())) + [0]
    d = [0] + list(map(int, input().split())) + [0]
    l = [0] + [i - 1 for i in range(1, n + 1)] + [n]
    r = [1] + [i + 1 for i in range(1, n + 1)] + [0]
    v = [0] * (n + 2)
    v[0] = v[n + 1] = 1
    q = []
    ans = [0] * n
    for i in range(1, n + 1):
        if a[l[i]] + a[r[i]] > d[i]:
            q.append(i)
    cur = 0
    while q:
        ans[cur] = len(q)
        for i in q:
            r[l[i]] = r[i]
            l[r[i]] = l[i]
            v[i] = 1
        nx = []
        for i in q:
            if not v[l[i]]:
                t = l[i]
                if a[l[t]] + a[r[t]] > d[t]:
                    nx.append(t)
                    v[t] = 1
            if not v[r[i]]:
                t = r[i]
                if a[l[t]] + a[r[t]] > d[t]:
                    nx.append(t)
                    v[t] = 1
        q = nx
        cur += 1
    print(*ans)
for _ in range(T):
    solve()

Solution (Python):
def kill_monsters(t):
    for _ in range(t):
        n = int(input())
        attack = [0] * (n + 2)
        defense = [0] * (n + 2)
        left = [0] * (n + 2)
        right = [0] * (n + 2)
        attack[1:n + 1] = map(int, input().split())
        defense[1:n + 1] = map(int, input().split())
        left[1:n + 1] = range(n)
        right[1:n + 1] = range(2, n + 2)
        alive_monsters = set(range(1, n + 1))
        for _ in range(n):
            dead = set()
            for i in alive_monsters:
                if 1 <= i <= n and attack[left[i]] + attack[right[i]] > defense[i]:
                    dead.add(i)
            alive_monsters.clear()
            for i in dead:
                alive_monsters.add(left[i])
                alive_monsters.add(right[i])
                left[right[i]] = left[i]
                right[left[i]] = right[i]
            alive_monsters -= dead
            print(len(dead), end=' ')
        print()
t = int(input())
kill_monsters(t)