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
#include <cstdio>
inline int min(int a, int b) { return (a<b?a:b); }
inline int max(int a, int b) { return (a>b?a:b); }
int main() {
    const int MOD = 1e9+7;
    int n;
    scanf("%d", &n);
    int dru[n+1], num[n+1], a[n+1], b[n+1];
    for (int i=1; i<=n; i++) scanf("%d%d", &a[i],&b[i]);
    dru[0] = 0, num[0] = 1;
    for (int i=1; i<=n; i++) {
        dru[i] = 0, num[i] = 0;
        int mini = a[i], maks = b[i];
        for (int j=i; j>0; j--) {
            mini = max(mini, a[j]);
            maks = min(maks, b[j]);
            if (i-j+1 > maks) break;
            if (i-j+1 >= mini) {
                if (dru[j-1]+1 > dru[i]) {
                    dru[i] = dru[j-1]+1;
                    num[i] = num[j-1];
                } else if (dru[j-1]+1 == dru[i])
                    num[i] = (num[i] + num[j-1]) % MOD;
            }
        }
    }
    if (dru[n] && num[n])
        printf("%d %d\n", dru[n],num[n]);
    else
        printf("NIE\n");
    return 0;
}