#include<iostream> #include<vector> #include<map> using namespace std; const int mx = 3e5 + 3; const int mod = 1e9 + 7; int n; long long a[mx], r[mx]; int pp[mx], pl[mx], np[mx]; vector<int>stos; map<pair<int, int>, long long>dp, bum, nie; long long oblicz(int poc, int kon); long long oblicz_bum(int poc, int kon) { if (poc > kon)return 1; if (bum[{poc, kon}])return bum[{poc, kon}]; if (np[poc]) { bum[{poc, kon}] = oblicz_bum(np[poc], kon); } else { bum[{poc, kon}] = oblicz(poc + 1, kon); } return bum[{poc, kon}]; } long long oblicz_nie(int poc, int kon) { if (kon - poc <= 1)return 1; if (nie[{poc, kon}])return nie[{poc, kon}]; if (pp[poc]!=0 && pp[poc] < kon&&poc!=1) { nie[{poc, kon}] = oblicz_nie(poc, pp[poc])*oblicz_nie(pp[poc], kon) % mod; } else if (pl[kon]>poc&&kon!=n) { nie[{poc, kon}] = oblicz_nie(poc, pl[kon])*oblicz_nie(pl[kon], kon) % mod; } else { nie[{poc, kon}] = oblicz(poc + 1, kon - 1); } return nie[{poc, kon}]; } long long oblicz(int poc, int kon) { if (poc > kon)return 1; if (dp[{poc, kon}])return dp[{poc, kon}]; if (np[poc]) { bum[{poc, kon}] = oblicz_bum(np[poc], kon); } else { bum[{poc, kon}] = oblicz(poc + 1, kon); } if (pp[poc]) { dp[{poc, kon}] = (oblicz_nie(poc, pp[poc])*oblicz_nie(pp[poc], kon) + bum[{poc, kon}]) % mod; } else { dp[{poc, kon}] = (oblicz(poc + 1, kon) + bum[{poc, kon}]) % mod; } return dp[{poc, kon}]; } int main() { ios::sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i] >> r[i]; } for (int i = n; i >= 1; --i) { while (!stos.empty() && a[stos.back()] - r[stos.back()]>a[i]) { stos.pop_back(); } if (!stos.empty()) { pp[i] = stos.back(); } stos.push_back(i); } stos.clear(); for (int i = 1; i <= n; ++i) { while (!stos.empty() && a[stos.back()] + r[stos.back()]<a[i]) { stos.pop_back(); } if (!stos.empty()) { pl[i] = stos.back(); np[stos.back()] = i; } stos.push_back(i); } stos.clear(); cout << oblicz(1, n) % mod; }
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 | #include<iostream> #include<vector> #include<map> using namespace std; const int mx = 3e5 + 3; const int mod = 1e9 + 7; int n; long long a[mx], r[mx]; int pp[mx], pl[mx], np[mx]; vector<int>stos; map<pair<int, int>, long long>dp, bum, nie; long long oblicz(int poc, int kon); long long oblicz_bum(int poc, int kon) { if (poc > kon)return 1; if (bum[{poc, kon}])return bum[{poc, kon}]; if (np[poc]) { bum[{poc, kon}] = oblicz_bum(np[poc], kon); } else { bum[{poc, kon}] = oblicz(poc + 1, kon); } return bum[{poc, kon}]; } long long oblicz_nie(int poc, int kon) { if (kon - poc <= 1)return 1; if (nie[{poc, kon}])return nie[{poc, kon}]; if (pp[poc]!=0 && pp[poc] < kon&&poc!=1) { nie[{poc, kon}] = oblicz_nie(poc, pp[poc])*oblicz_nie(pp[poc], kon) % mod; } else if (pl[kon]>poc&&kon!=n) { nie[{poc, kon}] = oblicz_nie(poc, pl[kon])*oblicz_nie(pl[kon], kon) % mod; } else { nie[{poc, kon}] = oblicz(poc + 1, kon - 1); } return nie[{poc, kon}]; } long long oblicz(int poc, int kon) { if (poc > kon)return 1; if (dp[{poc, kon}])return dp[{poc, kon}]; if (np[poc]) { bum[{poc, kon}] = oblicz_bum(np[poc], kon); } else { bum[{poc, kon}] = oblicz(poc + 1, kon); } if (pp[poc]) { dp[{poc, kon}] = (oblicz_nie(poc, pp[poc])*oblicz_nie(pp[poc], kon) + bum[{poc, kon}]) % mod; } else { dp[{poc, kon}] = (oblicz(poc + 1, kon) + bum[{poc, kon}]) % mod; } return dp[{poc, kon}]; } int main() { ios::sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i] >> r[i]; } for (int i = n; i >= 1; --i) { while (!stos.empty() && a[stos.back()] - r[stos.back()]>a[i]) { stos.pop_back(); } if (!stos.empty()) { pp[i] = stos.back(); } stos.push_back(i); } stos.clear(); for (int i = 1; i <= n; ++i) { while (!stos.empty() && a[stos.back()] + r[stos.back()]<a[i]) { stos.pop_back(); } if (!stos.empty()) { pl[i] = stos.back(); np[stos.back()] = i; } stos.push_back(i); } stos.clear(); cout << oblicz(1, n) % mod; } |