Niestety, nie byliśmy w stanie w pełni poprawnie wyświetlić tego pliku, ponieważ nie jest zakodowany w UTF-8. Możesz pobrać ten plik i spróbować otworzyć go samodzielnie. 
  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
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int M = 1048576;
const int DM = 2097152;

int n, N, a, b, poprzednik, g;
int C[2100000];
int D[2100000];
int W[2100000];

int liczba[1000005];
int sposoby[1000005];
int nieujemne[1000005];
int wynik[1000005];

int s;
const int INF = 1000000001;

// MaxTree z "Algorytmiki praktycznej" Piotra Sta�czyka
    
    void Set(int p,int v) {
	for(p+=s, W[p]=v, p>>=1; p>0; p>>=1)
	    W[p] = max(W[p<<1], W[(p<<1)+1]);
    }
	
	int Find1(int p, int k) {
	int m = -INF;
	p+=s; k+=s;
	while(p<k) {
	    if((p&1)==1) m=max(m,C[p++]);
	    if((k&1)==0) m=max(m,C[k--]);
	    p>>=1; k>>=1;
	}
	if(p==k) m=max(m,C[p]);
	return m;
    }
    
    int Find2(int p, int k) {
	int m = INF;
	p+=s; k+=s;
	while(p<k) {
	    if((p&1)==1) m=min(m,D[p++]);
	    if((k&1)==0) m=min(m,D[k--]);
	    p>>=1; k>>=1;
	}
	if(p==k) m=min(m,D[p]);
	return m;
    }

// MaxTree z "Algorytmiki praktycznej" Piotra Sta�czyka

int main ()
{
	s = M;
	scanf("%d",&n);
	N = n + M;
	for (int i = M; i < N; ++i) scanf("%d%d",&C[i],&D[i]);
	for (int i = M - 1; i > 0; --i) C[i] = max(C[i << 1], C[(i << 1) | 1]);
	for (int i = N; i < DM; ++i) D[i] = INF;
	for (int i = M - 1; i > 0; --i) D[i] = min(D[i << 1], D[(i << 1) | 1]);
	for (int i = 1; i < DM; ++i) W[i] = -1;
	sposoby[n] = 1;
	nieujemne[n] = n;
	Set(n, 0);
	for (int i = 0; i < n; ++i) liczba[i] = -1;
	for (int i = n - 1; i >= 0; --i)
	{
		a = 0;
		b = n;
		poprzednik = i;
		for (int j = i + 1; j <= n; )
		{
			j = nieujemne[j];
			if (liczba[i] > wynik[j] + 1) break;
			int g = j + s;
			while (W[g] < liczba[i] - 1)
			{
				if (g & 1) g++;
				else (g >>= 1);
			}
			while (g < s)
			{
				g <<= 1;
				if (W[g] < liczba[i] - 1) g |= 1;
			}
			j = g - s;
			a = max(a, Find1(poprzednik, j - 1));
			b = min(b, Find2(poprzednik, j - 1));
			poprzednik = j;
			if (a > b) break;
			if (b < j - i) break;
			if (j - i < a)
			{
				j = a + i;
				continue;
			}
			if (liczba[j] >= liczba[i])
			{
				liczba[i] = liczba[j] + 1;
				sposoby[i] = sposoby[j];
			}
			else
			{
				sposoby[i] += sposoby[j];
				if (sposoby[i] >= 1000000007) sposoby[i] -= 1000000007;
			}
			j++;
		}
		if (liczba[i] == -1) nieujemne[i] = nieujemne[i + 1];
		else nieujemne[i] = i;
		if (liczba[i] > wynik[i + 1]) wynik[i] = liczba[i];
		else wynik[i] = wynik[i + 1];
		if (liczba[i] != -1) Set(i, liczba[i]);
	}
	if (liczba[0] == -1) printf("NIE\n");
	else printf("%d %d\n", liczba[0], sposoby[0]);
	return 0;
}