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 #include #include #include #include #include #include #include #define REP(i, n) for(int i = 0; i < n; i++) #define FWD(i, a, b) for(int i = a; i < b; i++) #define ALL(u) (u).begin(), (u).end() using namespace std; typedef pair PII; typedef long long LL; typedef uint uint; const int INF = 1000000000; struct interval { int first, last, h; interval(int _first, int _last, int _h) { assert(_first <= _last); first = _first; last = _last; h = _h; } int len() { return last - first + 1; } void print() { printf("(f:%d l:%d h:%d) ", first, last, h); } }; class Sol { int n; vector plow, phigh; vector teams; vector ways; public: void sol() { scanf("%d", &n); plow.resize(n); phigh.resize(n); teams.resize(n+1, -1); ways.resize(n+1, 0); teams.back() = 0; ways.back() = 1; REP(i, n) { scanf("%d %d", &plow[i], &phigh[i]); } const LL mod = 1000000007; for(int pid = n-1; pid >= 0; pid--) { int cur_low = plow[pid], cur_high = phigh[pid]; int best = -1; for(int end = pid+1; end <= n; end++) { cur_low = max(plow[end-1], cur_low); cur_high = min(phigh[end-1], cur_high); if (end - pid >= cur_low and end - pid <= cur_high) { best = max(best, teams[end]); } if (end - pid > cur_high) { break; } } if (best == -1) continue; teams[pid] = best + 1; LL w = 0; cur_low = plow[pid]; cur_high = phigh[pid]; for(int end = pid+1; end <= n; end++) { cur_low = max(plow[end-1], cur_low); cur_high = min(phigh[end-1], cur_high); if (end - pid >= cur_low and end - pid <= cur_high) { if (teams[end] == best) { w += ways[end]; w %= mod; } } if (end - pid > cur_high) { break; } } ways[pid] = w; } if (teams[0] == -1) { printf("NIE\n"); } else { printf("%d %lld\n", teams[0], ways[0]); } } }; int main() { Sol s; s.sol(); return 0; }