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
#include <cstdio>
#include <algorithm>
using namespace std;

pair<int, int> t[1000000];

int c[1000000];
int d[1000000];

pair<int, int> combine(pair<int, int> a, pair<int, int> b)
{
    if(a.first == b.first) return make_pair(a.first, (a.second + b.second) % 1000000007);
    return max(a, b);
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
	scanf("%d %d", c + i, d + i);
    for(int i = 0; i < n; i++)
    {
	int low = c[i], up = d[i];
	for(int j = i - 1; j >= 0; j--)
	{
	    if(i - j > up) break;
	    if(t[j].first && i - j >= low)
		t[i] = combine(t[i], t[j]);
	    low = max(low, c[j]);
	    up = min(up, d[j]);
	}
	if(t[i].first) t[i].first++;
	else if(i + 1 >= low && i + 1 <= up)
	    t[i] = make_pair(1, 1);
    }
    if(t[n-1].first == 0) puts("NIE");
    else printf("%d %d\n", t[n-1].first, t[n-1].second);
}