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
#include <cstdio>
#include <vector>
using namespace std;
int p[1000005][2], f[1000005][2], n, MOD = 1000000007, mi, ma;
int main(){
    scanf("%d",&n);
    f[0][1] = 1;
    for (int i = 1; i <= n; i++){
        scanf("%d%d",&p[i][0],&p[i][1]);
        f[i][0] = -1;
    }
    for (int i = 1; i <= n; i++){
        mi = p[i][0], ma = p[i][1];
        for (int j = i-1; j >= 0; j--){
            if ( i-j > ma ){
                break;
            }
            else if (( f[j][0] != -1 ) && ( mi <= i-j ) && (i-j <= ma)){
                if ( f[j][0] + 1 > f[i][0] ){
                    f[i][0] = f[j][0] + 1;
                    f[i][1] = f[j][1];
                }
                else if ( f[j][0] + 1 == f[i][0] ){
                    f[i][1] = ( f[i][1] + f[j][1] ) % MOD;
                }
            }
            mi = max( mi, p[j][0] );
            ma = min( ma, p[j][1] );
        }
    }
    if (f[ n ][ 0 ] == -1){
        printf("NIE\n");
    }
    else {
        printf("%d %d\n", f[ n ][ 0 ], f[ n ][ 1 ]);
    }
}