Problem statement
There are N (<=100000) strips of something (say paper). Initially all of them are painted white. You'll be given some queries, two types of them.
1. Paint a range (a, b) with color x (x<=30)
2. Print the number of different colors in range (a,b)
A really nice problem. Another segment tree problem which requires lazy propagation. I wrote a solution with keeping an array of bools for each color in each node. At first it got couple of WA: I didn't really read the input specification thoroughly. There can be some queries with a>b. It again got WA, I carefully checked the code and realized that my query function wasn't returning anything! (It was returning the correct output, thanks to the stack) A quick fix brought a TLE. I realized that the array of bools can be replaced by a bitmask of int (as there can be as many as 30 colors). That change finally made it AC.
Here is the code.
Mistakes:
1. Not reading the problem statement carefully.
2. Trying to finish the code in a hurry after getting the idea.
3. Forgetting to put return statement.
There are N (<=100000) strips of something (say paper). Initially all of them are painted white. You'll be given some queries, two types of them.
1. Paint a range (a, b) with color x (x<=30)
2. Print the number of different colors in range (a,b)
A really nice problem. Another segment tree problem which requires lazy propagation. I wrote a solution with keeping an array of bools for each color in each node. At first it got couple of WA: I didn't really read the input specification thoroughly. There can be some queries with a>b. It again got WA, I carefully checked the code and realized that my query function wasn't returning anything! (It was returning the correct output, thanks to the stack) A quick fix brought a TLE. I realized that the array of bools can be replaced by a bitmask of int (as there can be as many as 30 colors). That change finally made it AC.
Here is the code.
Mistakes:
1. Not reading the problem statement carefully.
2. Trying to finish the code in a hurry after getting the idea.
3. Forgetting to put return statement.
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন