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
/*************************************************************************
 *   Zadanie:           Druzny                                           *
 *   Zlozonosc czasowa: O(n^2 log n)                                     *
 *   Wynik:             --/10                                            *
 *************************************************************************/

#include <iostream>
#include <vector>
#include <algorithm>

#define FOR(i,b,e) for(int i=(b); i <= (e); ++i)
#define FORD(i,b,e) for(int i=(b); i >= (e); --i)
#define SIZE(c) (int) (c).size()
#define FOREACH(i,c) FOR(i,0,SIZE(c)-1)
#define FORDEACH(i,c) FORD(i,SIZE(c)-1,0)
#define MIN(x,y) ( ((x) < (y))? (x) : (y) )
#define MAX(x,y) ( ((x) > (y))? (x) : (y) )
#define PB push_back

#define INF 2000000
#define MOD 1000000007
#define par(x) ( (x-1)/2 )

using namespace std;

int F(int x, int y, int t)
{
    if (t) return MIN(x,y);
    else return MAX(x,y);
}

int p = 1;
vector < int > T[2]; //drzewo minimow i maximow

int Query(int l, int r, bool t) //0 - max, 1 - min
{
    l += p-1;
    r += p-1;

    int ans = F(T[t][l],T[t][r],t);

    while (par(l) != par(r))
    {
        if (l%2 == 1) ans = F(ans,T[t][l+1],t);
        if (r%2 == 0) ans = F(ans,T[t][r-1],t);

        l = par(l);
        r = par(r);
    }

    return ans;
}

bool IsGood(int l, int r)//czy przedzial [l,r] tworzy druzyne
{
    int c = Query(l,r,0), d = Query(l,r,1), k = r - l + 1;

    return ((k >= c) && (k <= d));
}

/*************************************************************************/

int main()
{
    ios_base::sync_with_stdio(0);

    int n;
    cin >> n;

    while (p < n) p *= 2;

    T[0].resize(2*p-1,0);
    T[1].resize(2*p-1,INF);

    FOR(i,p-1,p+n-2) FOR(j,0,1)
        cin >> T[j][i];

    FORD(i,p-2,0) FOR(j,0,1)
        T[j][i] = F(T[j][2*i+1],T[j][2*i+2],j);

    vector < int > D(n,0);
    vector < int > cnt(n,0);

    FOREACH(i,D)
    {
        int left = MAX(0,i+1-T[1][i+p-1]), right = MAX(0,i+1-T[0][i+p-1]);

        FOR(j,left,right) if(IsGood(j,i) && (j == 0 || D[j-1] > 0))
        {
            int num = 1 + ((j == 0)? 0 : D[j-1]);

            if (num > D[i])
            {
                D[i] = num;
                cnt[i] = ((j == 0)? 1 : cnt[j-1]);
            }
            else if (num == D[i])
                cnt[i] = (cnt[i] + cnt[j])%MOD;
        }
    }

    if (D[n-1] == 0)
        cout << "NIE";
    else
        cout << D[n-1] << ' ' << cnt[n-1];

    return 0;
}

/*************************************************************************/