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 nonoverlapping classes to attend. A subset is nonoverlapping 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 nonoverlapping nonempty 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 ≤ 10^{5} ). 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 ≤ 10^{9} ). 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
nonoverlapping nonempty 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
hide comments
dkkv0000:
20200119 19:21:08
AFTER 10 WA AC (0.16)


ayushjais2654:
20200119 13:42:20
Doing sort and then O(nlogn) still showing TLE .. 

rising_stark:
20191230 22:42:46
I am doing a sort, then a loop and within it just a binary search but getting TLE still. Plz help.


sagar_june97p:
20190611 17:20:23
For output format, use setfill() with setw() in C++.


shehar48:
20190518 21:21:42
@ankur1999


kumar18tushar:
20190515 09:39:51
take care of MOD , costed me 2 wa 

prabhudeen:
20190507 21:22:43
accepted in one go ! 

hocky:
20190417 06:58:39
3*(nlogn) still gives 0.09 

ab_biswas09:
20190317 20:57:08
AC in one go >> nlogn >> 0.30 sec 

ankur1999:
20190202 10:32:45
How to do this in O(nlogn) , please help. My solution has complexity O(n^2) 
Added by:  Pablo Ariel Heiber 
Date:  20100924 
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 