#include <bits/stdc++.h> #define ll long long int #define pb push_back #define st first #define nd second #define pii pair<int,int> #define mp make_pair #define pll pair<long long,long long> using namespace std; const int nax = 5005; ll a[nax]; ll r[nax]; int n; int LOW[nax][22]; int HIGH[nax][22]; int dp[nax][2]; pii inter[nax]; vector<int> endzik[nax]; const int bits = 1445; bitset<bits> dkd[bits]; bitset<bits> prefix[bits]; const int mod = 1e9 + 7; void solve() { for(int i=0;i<bits;i++) prefix[0].flip(i); for(int i=1;i<bits;i++) { prefix[i] = prefix[i - 1]; prefix[i].flip(i); } cin>>n; for(int i=1;i<=n;i++) cin>>a[i]>>r[i]; for(int i=1;i<=n;i++) { ll to_low = a[i] - r[i]; ll to_high = a[i] + r[i]; int wsk = i; while(wsk > 1 && a[wsk - 1] >= to_low) wsk--; LOW[i][0] = wsk; wsk = i; while(wsk < n && a[wsk + 1] <= to_high) wsk++; HIGH[i][0] = wsk; } for(int j=1;j<=13;j++) { for(int i=1;i<=n;i++) { int lo = LOW[i][j - 1]; int hi = HIGH[i][j - 1]; int mini = 1e9; int maxi = -1e9; for(int c=lo;c<=hi;c++) { int cmini = LOW[c][j - 1]; int cmaxi = HIGH[c][j - 1]; mini = min(mini,cmini); maxi = max(maxi,cmaxi); } LOW[i][j] = mini; HIGH[i][j] = maxi; } } vector<pii> intervals; for(int i=1;i<=n;i++) { inter[i] = mp(LOW[i][13],HIGH[i][13]); } for(int i=1;i<=n;i++) { pii cur = inter[i]; endzik[cur.st].pb(cur.nd); } for(int i=1;i<=n;i++) sort(endzik[i].begin(),endzik[i].end()); for(int i=n;i>=1;i--) { int to = i - 2; for(int x : endzik[i]) to = max(to ,x); int mini = 1e9; for(int x : endzik[i]) { dkd[i].set(x); } int wsk = 0; for(int j=i;j<=to + 1;j++) { int last = 1e9; while(wsk < endzik[i].size() && endzik[i][wsk] < j - 1) wsk++; last = endzik[i][wsk]; dkd[i] |= (dkd[j] & prefix[last - 1]); } } dp[n + 1][0] = 1; for(int i=n;i>=1;i--) { dp[i][0] = dp[i + 1][0] + dp[i + 1][1]; dp[i][0] %= mod; for(int x=0;x<bits;x++) { if(dkd[i][x] == 0) continue; dp[i][1] += dp[x + 1][0]; dp[i][1] %= mod; } } cout<<((dp[1][0] + dp[1][1]) % mod)<<" "; } int main() { solve(); return 0; }
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 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 | #include <bits/stdc++.h> #define ll long long int #define pb push_back #define st first #define nd second #define pii pair<int,int> #define mp make_pair #define pll pair<long long,long long> using namespace std; const int nax = 5005; ll a[nax]; ll r[nax]; int n; int LOW[nax][22]; int HIGH[nax][22]; int dp[nax][2]; pii inter[nax]; vector<int> endzik[nax]; const int bits = 1445; bitset<bits> dkd[bits]; bitset<bits> prefix[bits]; const int mod = 1e9 + 7; void solve() { for(int i=0;i<bits;i++) prefix[0].flip(i); for(int i=1;i<bits;i++) { prefix[i] = prefix[i - 1]; prefix[i].flip(i); } cin>>n; for(int i=1;i<=n;i++) cin>>a[i]>>r[i]; for(int i=1;i<=n;i++) { ll to_low = a[i] - r[i]; ll to_high = a[i] + r[i]; int wsk = i; while(wsk > 1 && a[wsk - 1] >= to_low) wsk--; LOW[i][0] = wsk; wsk = i; while(wsk < n && a[wsk + 1] <= to_high) wsk++; HIGH[i][0] = wsk; } for(int j=1;j<=13;j++) { for(int i=1;i<=n;i++) { int lo = LOW[i][j - 1]; int hi = HIGH[i][j - 1]; int mini = 1e9; int maxi = -1e9; for(int c=lo;c<=hi;c++) { int cmini = LOW[c][j - 1]; int cmaxi = HIGH[c][j - 1]; mini = min(mini,cmini); maxi = max(maxi,cmaxi); } LOW[i][j] = mini; HIGH[i][j] = maxi; } } vector<pii> intervals; for(int i=1;i<=n;i++) { inter[i] = mp(LOW[i][13],HIGH[i][13]); } for(int i=1;i<=n;i++) { pii cur = inter[i]; endzik[cur.st].pb(cur.nd); } for(int i=1;i<=n;i++) sort(endzik[i].begin(),endzik[i].end()); for(int i=n;i>=1;i--) { int to = i - 2; for(int x : endzik[i]) to = max(to ,x); int mini = 1e9; for(int x : endzik[i]) { dkd[i].set(x); } int wsk = 0; for(int j=i;j<=to + 1;j++) { int last = 1e9; while(wsk < endzik[i].size() && endzik[i][wsk] < j - 1) wsk++; last = endzik[i][wsk]; dkd[i] |= (dkd[j] & prefix[last - 1]); } } dp[n + 1][0] = 1; for(int i=n;i>=1;i--) { dp[i][0] = dp[i + 1][0] + dp[i + 1][1]; dp[i][0] %= mod; for(int x=0;x<bits;x++) { if(dkd[i][x] == 0) continue; dp[i][1] += dp[x + 1][0]; dp[i][1] %= mod; } } cout<<((dp[1][0] + dp[1][1]) % mod)<<" "; } int main() { solve(); return 0; } |