1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>      

using namespace std;

struct Child{
    int min;
    int max;
};

struct Division{
    int maxGroupsBefore;
	int combinationsOfMaxGroups;
    Division(){
        this->maxGroupsBefore = 0;
		this->combinationsOfMaxGroups = 0;
    }
};

int main () {
    int childrenAmount;
	cin >> childrenAmount;
	Child* children = new Child[childrenAmount];
	Division* divisions = new Division[childrenAmount+1];
	divisions[0].combinationsOfMaxGroups = 1;
	const int mod = 1000000007;

	for(int i=0; i<childrenAmount; i++){
		cin >> children[i].min >> children[i].max;
	}
	for(int divisionId=0; divisionId<childrenAmount; divisionId++){
		int newCombinations = divisions[divisionId].combinationsOfMaxGroups;
		if(newCombinations + divisions[divisionId].maxGroupsBefore > 0){
			int newMaxGroups = divisions[divisionId].maxGroupsBefore + 1;
			int counter = 1;
			int min = children[divisionId].min;
			int max = children[divisionId].max;
			bool noMoreGroups = false;
			do{
				if(counter >= min){ //max is checked later, for sure in first iteration max >= counter
					Division* goalDivision = &divisions[divisionId+counter];
					if(goalDivision->maxGroupsBefore < newMaxGroups){
						goalDivision->maxGroupsBefore = newMaxGroups;
						goalDivision->combinationsOfMaxGroups = newCombinations;
					}
					else if(goalDivision->maxGroupsBefore == newMaxGroups){
						goalDivision->combinationsOfMaxGroups = (goalDivision->combinationsOfMaxGroups + newCombinations) % mod;
					}
				}
				if(divisionId + counter < childrenAmount){
					if(children[divisionId+counter].min > min) min = children[divisionId+counter].min;
					if(children[divisionId+counter].max < max) max = children[divisionId+counter].max;
					counter++;
					if(counter > max) noMoreGroups = true;
				}
				else noMoreGroups = true;
			}while(!noMoreGroups);
		}
	}
	if(divisions[childrenAmount].maxGroupsBefore > 0){
		cout << divisions[childrenAmount].maxGroupsBefore << " " << divisions[childrenAmount].combinationsOfMaxGroups;
	}
	else cout << "NIE\n";

	delete [] children;
	delete [] divisions;
	return 0;
};