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.


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.


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.


1 3
3 5
5 7
2 4
4 6
500000000 1000000000
1 500000000
1 500000000
999999999 1000000000
-1 Output:

hide comments
harshh3010: 2021-03-22 21:06:35

use setw(8) and setfill('0') for output in c++

lamda_cdm_10: 2020-09-20 05:22:38

remember to take mod of 10^8 ,costed me 3 WA for that

pacific_kafka: 2020-08-23 15:57:56

Dynamic Programming makes me feels sad

vakulsingh: 2020-07-30 13:41:23

just take mod 10^8 at every dp step,somehow did'not see that for a long time

jopdhiwaala: 2020-05-16 11:45:04

You could do to_string in c++ and output the characters.

pallindromeguy: 2020-03-29 10:00:27

Cost me 2 WA because I was taking mod 10^8+7 instead of just 10^8 :(

dkkv0000: 2020-01-19 19:21:08

AFTER 10 WA AC (0.16)
1) for those who are facing TLE use pass by reference it solved the problem in my case

ayushjais2654: 2020-01-19 13:42:20

Doing sort and then O(nlogn) still showing TLE ..

rising_stark: 2019-12-30 22:42:46

I am doing a sort, then a loop and within it just a binary search but getting TLE still. Plz help.
Here is the link to my code:

sagar_june97p: 2019-06-11 17:20:23

For output format, use setfill() with setw() in C++.
Also use mod 10^8.
Don't use 10^9. It gave me 2 WAs. :(

Last edit: 2019-06-11 17:22:16

Added by:Pablo Ariel Heiber
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