Submit | All submissions | Best solutions | Back to list |
ACTIV - Activities |
Ana likes many activities. She likes acrobatics, alchemy, archery, art, Arabic dances, and many more. She joined a club that offers several classes. Each class has a time interval in every week. Ana wants to sign up for many classes, but since they overlap in time, she looks for a subset of non-overlapping classes to attend. A subset is non-overlapping if it does not contain two classes that overlap in time. If a class starts at the time another class ends, this is not considered overlapping.
Ana decided to list all the non-overlapping non-empty subsets of classes. Then she will choose the subset she likes best. In order to predict the amount of paper needed to write the list, she wants you to calculate how many of these subsets there are.
Input
Each test case is described using several lines. The first line contains an integer N indicating the number of classes the club offers (1 ≤ N ≤ 105). Each of the next N lines describes a class using two integers S and E that represent the starting and ending times of the class, respectively (1 ≤ S < E ≤ 109). The end of input is indicated with a line containing a single −1.
Output
For each test case, output a single line with a single integer representing the number of non-overlapping non-empty subsets of classes. To make your life easier, output only the last 8 digits of the result. If the result has less than 8 digits, write it with leading zeros to complete 8 digits.
Example
Input: 5 1 3 3 5 5 7 2 4 4 6 3 500000000 1000000000 1 500000000 1 500000000 1 999999999 1000000000 -1 Output: 00000012 00000005 00000001
Added by: | Pablo Ariel Heiber |
Date: | 2010-09-24 |
Time limit: | 2.365s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 NODEJS OBJC VB.NET |
Resource: | FCEyN UBA ICPC Selection 2010 |
hide comments
|
|||||||
2018-10-07 11:53:38
AC in one go :) |
|||||||
2018-07-06 08:53:20
mod=10^8 is correct to retain last 8 digits.............. |
|||||||
2018-06-04 20:04:35
costed 1 WA for @learnerinblack. :3 Ignore his message. Take modulo 1e8. |
|||||||
2018-06-02 09:29:31
Use 10^9 as modulo. Costed me 2 WAs |
|||||||
2018-05-21 13:18:19
Can also be done using compression and BIT! Complexity O(NlgN) Last edit: 2018-05-21 13:19:01 |
|||||||
2018-03-01 08:07:28
learnt how to use upper_bound on structure! , good one! |
|||||||
2017-08-30 10:34:49
I keep getting SIGXFSZ error :| Wiki says that this signal indicates I am exceeding output file size. I don't understand why such a thing may be happening. Please look into it : Submission Id - 20064346 |
|||||||
2017-06-19 21:30:37
O(2*nlogn) executes in 0.14 |
|||||||
2017-05-24 21:25:04
easy but take care of the modulus .. |
|||||||
2017-01-25 19:41:50
can any one help my code gives wrong ans in O(nlogn + nlogn) implementation |