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
#include <iostream>
#include <cstring>

using namespace std;

const int N=1000000, M=1000000007;
int n, c[N+1], d[N+1], ld[N+1], ls[N+1];

int main()
{
  ios_base::sync_with_stdio(false);
  cin>>n;
  for (int i=1; i<=n; ++i)
    cin>>c[i]>>d[i];
  ld[0]=ls[0]=1;
  for (int zaw=1; zaw<=n; ++zaw)
    if (ld[zaw-1])
    {
//      if ((zaw&1023)==0)
//        cerr<<zaw<<endl;
      for (int z=zaw, lz=0, mi=0, ma=N; z<=n; ++z)
      {
        ++lz;
        mi=max(mi, c[z]);
        ma=min(ma, d[z]);
        if (ma<mi || ma<lz)
          break;
        if (mi<=lz)
        {
          int x=ld[zaw-1]+1;
          if (ld[z]<x)
          {
            ld[z]=x;
            ls[z]=ls[zaw-1];
          }
          else if (ld[z]==x)
          {
            ls[z]+=ls[zaw-1];
            if (ls[z]>=M)
              ls[z]-=M;
          }
        }
      }    
    }
  if (ld[n]) cout<<(ld[n]-1)<<' '<<ls[n]<<endl;
  else cout<<"NIE"<<endl;
  return 0;
}