Submission #1235055

#TimeUsernameProblemLanguageResultExecution timeMemory
1235055faricaTrains (BOI24_trains)C++20
58 / 100
211 ms137440 KiB
#include<bits/stdc++.h> using namespace std; using vi = vector<int>; using pi = pair<int,int>; typedef long long ll; #define debug(x) cout << #x << " = " << x << "\n"; #define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n"; const int MOD = 1e9 + 7; const int INF = 1e9; template<ll mod> struct modnum { static constexpr bool is_big_mod = mod > numeric_limits<int>::max(); using S = conditional_t<is_big_mod, ll, int>; using L = conditional_t<is_big_mod, __int128, ll>; S x; modnum() : x(0) {} modnum(ll _x) { _x %= static_cast<ll>(mod); if (_x < 0) { _x += mod; } x = _x; } modnum pow(ll n) const { modnum res = 1; modnum cur = *this; while (n > 0) { if (n & 1) res *= cur; cur *= cur; n /= 2; } return res; } modnum inv() const { return (*this).pow(mod-2); } modnum& operator+=(const modnum& a){ x += a.x; if (x >= mod) x -= mod; return *this; } modnum& operator-=(const modnum& a){ if (x < a.x) x += mod; x -= a.x; return *this; } modnum& operator*=(const modnum& a){ x = static_cast<L>(x) * a.x % mod; return *this; } modnum& operator/=(const modnum& a){ return *this *= a.inv(); } friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; } friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; } friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; } friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; } friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; } friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; } friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; } friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; } friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; } }; using mint = modnum<MOD>; template <class T> class SumSegmentTree { private: const T DEFAULT = 0; vector<T> segtree; int len; public: SumSegmentTree(int len) : len(len), segtree(len * 2, DEFAULT) {} void set(int ind, T val) { ind += len; segtree[ind] = val; for (; ind > 1; ind /= 2) { segtree[ind / 2] = segtree[ind] + segtree[ind ^ 1]; } } T range_sum(int start, int end) { T sum = DEFAULT; for (start += len, end += len; start < end; start /= 2, end /= 2) { if (start % 2 == 1) { sum += segtree[start++]; } if (end % 2 == 1) { sum += segtree[--end]; } } return sum; } }; struct DSU{ vector<int> p, sz, used, mn, mx; DSU(int n){ p.assign(n, 0); sz.assign(n, 1); used.assign(n, 0); mx.assign(n, 0); mn.assign(n, 0); for (int i = 0; i < n; i++) p[i] = i; } int find(int u){ if (p[u] == u) return u; p[u] = find(p[u]); return p[u]; } void unite(int u, int v){ u = find(u); v = find(v); if (u == v) return; if (sz[u] < sz[v]) swap(u, v); p[v] = u; sz[u] += sz[v]; used[u] += used[v]; mn[u] = min(mn[u], mn[v]); mx[u] = max(mx[u], mx[v]); } bool same(int u, int v){ return find(u) == find(v); } int size(int u){ u = find(u); return sz[u]; } }; const int N = 250005; /*struct BIT { ll b[N], n; void init(int _n) { n = _n ; for(int i = 0 ; i <= n ; ++i) b[i] = INF; } inline int lowbit(int x) { return x & (-x); } void update(int x, ll v) { for(int i = x ; i <= n ; i += lowbit(i)) b[i] = min(v, b[i]); } ll query(int x) { ll ans = INF; for(int i = x ; i > 0 ; i -= lowbit(i)) ans = min(ans,b[i]); return ans; } } bit[2];*/ int gcd(int a, int b, int& x, int& y) { // x*a + y*b = a1 x = 1, y = 0; int x1 = 0, y1 = 1, a1 = a, b1 = b; while (b1) { int q = a1 / b1; tie(x, x1) = make_tuple(x1, x - q * x1); tie(y, y1) = make_tuple(y1, y - q * y1); tie(a1, b1) = make_tuple(b1, a1 - q * b1); } return a1; } int inv_ecd(int a, int m) { int x, y; int g = gcd(a, m, x, y); if(g != 1) return -1; x = (x + m) % m; return x; } const int B = 320; ll mem[B][B]; void solve() { int n; cin >> n; vector<ll> d(n), x(n), dp(n, 0); dp[0] = 1; for(int i=0; i<n; ++i) { cin >> d[i] >> x[i]; } /*for(auto it = ma.begin(); it != ma.end(); ++it) { vi v = it->second; int cur = it->first; if(cur > B) { for(int a: v) { ll R = n-1, rght = a + cur * x[a]; for(int j=a+cur; j<=min(R,rght); j+=cur) dp[j] = (dp[j] + dp[j-cur]) % MOD; } } else { int cnt = 0; vi tmp(cur, 0), rem(n, 0); for(int i=0; i<n; ++i) { dp[i] = (dp[i] + tmp[i%cur]) % MOD; if(cnt != (int)v.size() && v[cnt] == i) { tmp[i%cur] = (tmp[i%cur] + dp[i]) % MOD; ll R = min((ll)n-1, i + 1ll * x[i] * cur); rem[R] = (rem[R] + dp[i]) % MOD; ++cnt; } tmp[i%cur] = (tmp[i%cur] - rem[i] + MOD) % MOD; } } }*/ queue<pair<ll,ll>>Q[n], rem[n]; for(int i=0; i<n; ++i) { for(int j=1; j<B; ++j) dp[i] = (dp[i] + mem[j][i%j]) % MOD; ll R = 1ll * x[i] * d[i] + i; R = min(R, (ll)n-1); if(d[i] >= B) Q[i].push({d[i], R}); else if(d[i]) { mem[d[i]][i%d[i]] = (mem[d[i]][i%d[i]] + dp[i]) % MOD; if(R != n-1) rem[R].push({i, dp[i]}); } while(!rem[i].empty()) { pair<ll,ll> cur = rem[i].front(); rem[i].pop(); int D = d[cur.first]; mem[D][cur.first%D] = (mem[D][cur.first%D] - cur.second + MOD) % MOD; } while(!Q[i].empty()) { pair<ll,ll> cur = Q[i].front(); Q[i].pop(); int nxt = i + cur.first; if(nxt > cur.second) continue; dp[nxt] = (dp[nxt] + dp[i]) % MOD; Q[nxt].push(cur); } } ll ans = 0; for(int i=0; i<n; ++i) { ans = (ans + dp[i]) % MOD; //cout << i << ": " << dp[i] << endl; } cout << ans << endl; } int main(){ //freopen("N3.in", "r", stdin); //freopen("N3.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tc=1; while (tc--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...