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
        ind[l].append(unique_val)
 
        # Negative denotes ending
        # We use r+1 because r is inclusive in the range
        ind[r+1].append(-unique_val)
 
        # 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=' ')
 
    print()

Pastebin link: Angry Cyborg - Pastebin.com
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:

2 Likes

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

2 Likes

Thanks for the suggestion!

1 Like

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

https://www.codechef.com/viewsolution/40944002

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

2 Likes
1
10 10
Output: aaaaaabaa

I believe it should be aaaaaaaaa

1 Like

thanks

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

https://www.codechef.com/viewsolution/40951304

@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
123
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