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
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long int ll;

const int mod = 1e9 + 7;

int mak[1000005];
int ile[1000005];

int n;

int c[1000005];
int d[1000005];

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d%d", c + i, d + i);
	reverse(c + 1, c + n + 1);
	reverse(d + 1, d + n + 1);
	mak[0] = 0;
	ile[0] = 1LL;
	for(int i = 1; i <= n; i++)
	{
		int mn = c[i], mx = d[i];
		for(int j = i; j >= 1; j--)
		{
			mn = max(mn, c[j]);
			mx = min(mx, d[j]);
			if(mn > mx || i - j + 1 > mx)
				break;
			if(i - j + 1 >= mn)
			{
				if(mak[i] == mak[j - 1] + 1)
					ile[i] = (ile[i] + ile[j - 1]) % mod;
				else if(mak[i] < mak[j - 1] + 1)
				{
					ile[i] = ile[j - 1];
					mak[i] = mak[j - 1] + 1;
				}
			}
		}
	}
	if(ile[n])
		printf("%d %d\n", mak[n], ile[n]);
	else
		printf("NIE\n");
	return 0;
}