|
|
вернуться в форум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 :) 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? |
|
|