Fish
Time limit1.5sMemory limit512 MB
Given N fish with lengths and one of three colors, count the distinct color-count triples achievable by a set of fish where no two have a length ratio of 2 or more.
- Level
Medium7 of 10
- Topics
- Sorting, Two pointers, Combinatorics
- Solved
- No attempts yet
Problem
JOI has suddenly decided to keep fish.
When he went to a pet shop near his house, N fish were for sale there. The length of the i-th fish is Li cm, and its color is one of red, green, or blue. JOI has decided to keep at least one of these N fish at home.
There is something to watch out for when keeping fish. If a large fish and a small fish are kept at the same time, the large fish will eat the small fish. Specifically, when the length of fish X is at least twice the length of fish Y, keeping X and Y at the same time means X will eat Y. Therefore, such two fish cannot be kept at the same time.
JOI became curious about how many combinations of colors of fish he might keep are possible. Two color combinations differ when the number of fish of at least one of the colors red, green, and blue differs. Given the lengths and colors of the fish sold at the pet shop, he wants to find the number of combinations of colors of fish he might keep.
Given the lengths and colors of the fish sold at the pet shop, write a program that outputs the number of combinations of colors of fish JOI might keep.
Input
Read the following input from standard input.
- The first line contains the integer N. N is the number of fish sold at the pet shop.
- The 1 + i-th line (1 ≤ i ≤ N) contains the integer Li and the character Ci separated by a space. The character Ci is one of R, G, B. This means the length of the i-th fish is Li cm, and if Ci is R the i-th fish is red, if Ci is G it is green, and if Ci is B it is blue.
Output
On standard output, print the number of combinations of colors of fish JOI might keep on one line.
Constraints
- 1 ≤ N ≤ 500 000, the number of fish
- 1 ≤ Li ≤ 1 000 000 000, the length of the i-th fish