মঙ্গলবার, ৮ ফেব্রুয়ারী, ২০১১

PKU 2777 - Count Color

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.

কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন