ByteRace Angry Cyborg Solution (Commented Code in Python)

For those who want the editorial sooner:

from collections import defaultdict
for _ in range(int(input())):
    n, q = map(int, input().split())
    # defaultdict(list) assigns the value as an empty list for each key by default
    # ind stores a unique value for each range
    ind = defaultdict(list)
    # Unique value for each range
    unique_val = 1
    for _ in range(q):
        l, r = map(int, input().split())
        # Converting to 0-based indexing
        l -= 1
        r -= 1
        # Positive denotes beginning
        # Negative denotes ending
        # We use r+1 because r is inclusive in the range
        # Next value to make it unique
        unique_val += 1
    no_sts = 0  # Number of statues that will be destroyed
    ispeed = 0  # Speed at which the number of statues destroyed increases
    # First occurrence of a range (stores l value of a range)
    occ = {}
    for i in range(n):
        # For each "endpoint" (which is l or r+1)
        for j in ind[i]:
            # If it's a new range the speed with which the number of statues is destroyed will increase
            if j > 0:
                occ[j] = i
                ispeed += 1
            # If it's the end of a range
            # The speed with which the number of statues is destroyed will decrease
            # The current amount of statues which are being destroyed at each index will decrease by how much it has contributed
            # Which is equal to r - l + 1, but since we set the endpoint to r+1, we should make it r - l
            # Here, (r = i) and (l = [first occurrence of -j] = occ[-j])
            elif j < 0:
                ispeed -= 1
                no_sts -= i - occ[-j]
        # The amount of statues destroyed at each index increases by the speed
        no_sts += ispeed
        print(no_sts, end=' ')

Pastebin link: Angry Cyborg -
CodeChef submission link: Solution: 40945043 | CodeChef

Time complexity: O(N+Q)
Space complexity: O(N+Q)

A C++ solution is under construction! C++ version here!

If you have any queries/suggestion, please let me know! :smile:


For those of us too tired to go through the code, could you add the time and space complexity of your solution?


Thanks for the suggestion!

1 Like

@crap_the_coder @inclusiveor
can you please check my code for cab

Line 5, the condition needs to be n>k not k>n.

10 10
Output: aaaaaabaa

I believe it should be aaaaaaaaa

1 Like


hi can you please check this code for cab , i am getting right output but the oj is showing WA for this

@amandikshit10 The specified link doesn’t redirects to your solution instead it redirects to New Submission page. Please check the link. :grinning_face_with_smiling_eyes:

1 Like
1 3
Output: b

The answer should be -1, since it’s impossible to get 3 with just one character.
Your program doesn’t check whether the final answer is correct, which is why the output is incorrect.

1 Like