If you have WA#3 check whether you have a correct understanding of updating:

(Thanks for Vit Demidenko (http://acm.timus.ru/author.aspx?id=74435)

Format:

UpdateType
 Source -> Destination
---
Pirated
 Licensed -> Pirated
 Pirated -> Pirated

Licensed
 Licensed -> Licensed

Cracked ->
 Pirated -> Pirated
 Licensed -> Licensed

I have WA#3 when I write a wrong interpretation of "Cracked" update.

P.S. About O(m*log(m)) solution:
1. Sort the updates by "yi" parameter ascending.
2. Then use dynamic programming.

You can even avoid sorting, simply create an array of linked lists and group the update read to the list with index 'y'. Then go through all of them from least 'y''s up to the greatest ones and use DP. This solution is O(m), if i've not mistaken :)

Yes, it is true. And the method you suggested, is counting sort (http://en.wikipedia.org/wiki/Counting_sort)
And if you use radix sort, you 'll need to make only one additional array of n elements (http://en.wikipedia.org/wiki/Radix_sort), and the complexity of your solution will remain O(m).

Edited by author 14.08.2011 16:08

Thanks, Leonid.
All linear-time sortings are almost the same and use the same idea. "Radix sort" uses less memory than "Counting sort", but it works some time longer. But since "n,m<=10^4", should we care about the memory we use?