fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define FOR(i,a,b)      for (int i = (a), _b = (b); i <= (_b); ++i)
  6. #define FORD(i,a,b)     for (int i = (a), _b = (b); i >= (_b); --i)
  7. #define REP(i, n)        for (int i = (0), _n = (n); i < _n; ++i)
  8. #define getBit(mask,i)  (((mask) >> (i)) & (1LL))
  9. #define MASK(x)            (1LL << (x))
  10. #define allof(x)        begin(x), end(x)
  11. #define el              cout << '\n';
  12.  
  13. //--Compare------------------------------------------------------------------------------------
  14. template<class X, class Y>
  15.     inline bool maximize(X &x, const Y &y){ return (x < y) ? x = y, 1 : 0; }
  16.  
  17. template<class X, class Y>
  18.     inline bool minimize(X &x, const Y &y){ return (x > y) ? x = y, 1 : 0; }
  19.  
  20. //--Process------------------------------------------------------------------------------------
  21.  
  22. #define int             long long
  23.  
  24. constexpr int MAXN = 2e5 + 10, MOD = 1e9 + 7;
  25.  
  26. inline void add(int &x, const int &y) { x += y; if (x >= MOD) x -= MOD; }
  27. inline int mul(const int &x, const int &y) { return 1LL * (x % MOD) * (y % MOD) % MOD; }
  28.  
  29. int n;
  30. int d[MAXN], x[MAXN];
  31.  
  32. namespace subtask1
  33. {
  34.     int dp[MAXN];
  35.  
  36.     void solve(void)
  37.     {
  38. //        if (!(n <= 10000)) return;
  39.  
  40.         dp[1] = 1;
  41.         int res = 0;
  42.         FOR(i, 1, n)
  43.         {
  44.             if (d[i])
  45.             FOR(j, 1, x[i])
  46.             {
  47.                 int t = i + j * d[i];
  48.                 if (t > n) break;
  49.                 add(dp[t], dp[i]);
  50.             }
  51.  
  52.             add(res, dp[i]);
  53.         }
  54.  
  55.         cout << res << '\n';
  56.  
  57.         cerr << 1;
  58.         exit(0);
  59.     }
  60. }
  61.  
  62. namespace subtask2
  63. {
  64.     int BIT[2][MAXN];
  65.  
  66.     void updatePoint(const bool &_, int id, const int &val)
  67.     {
  68.         if (id <= 0) return;
  69.         for (; id <= n; id += id & -id) add(BIT[_][id], val);
  70.     }
  71.  
  72.     void update(const int &l, const int &r, int val)
  73.     {
  74.         if (l > n || r > n || l > r) return;
  75.  
  76.         val = (val + MOD) % MOD;
  77.  
  78.         updatePoint(0, l, val);
  79.         updatePoint(0, r + 1, MOD - val);
  80.         updatePoint(1, l, mul((l - 1 + MOD * MOD) % MOD, val));
  81.         updatePoint(1, r + 1, mul((MOD * MOD - r) % MOD, val));
  82.     }
  83.  
  84.     inline int getPrefix(const bool &_, int id)
  85.     {
  86.         if (id <= 0) return 0;
  87.         int res = 0;
  88.         for (; id; id -= id & -id) add(res, BIT[_][id]);
  89.         return res;
  90.     }
  91.  
  92.     inline int get(int l, int r)
  93.     {
  94.         int x = (l > 1) ? (mul(getPrefix(0, l - 1), l - 1) - getPrefix(1, l - 1) + MOD) % MOD : 0;
  95.         int y = (mul(getPrefix(0, r), r) - getPrefix(1, r) + MOD * MOD) % MOD;
  96.  
  97.         return (y - x + MOD) % MOD;
  98.     }
  99.  
  100.     void solve(void)
  101.     {
  102.         if (*max_element(d + 1, d + n + 1) > 1) return;
  103.  
  104.         int res = 0;
  105.         update(1, 1, 1);
  106.  
  107.         FOR(i, 1, n)
  108.         {
  109.             int cur = get(i, i);
  110.             if (d[i])
  111.             {
  112.                 int L = i + 1, R = min(n, i + x[i]);
  113.                 update(L, R, cur);
  114.             }
  115.  
  116.             add(res, cur);
  117.         }
  118.  
  119.         cout << res << '\n';
  120.  
  121.         cerr << 2;
  122.         exit(0);
  123.     }
  124. }
  125.  
  126. namespace subtask4
  127. {
  128.     constexpr int BLOCK_SZ = 447;
  129.     int dp[MAXN];
  130.     int lz[BLOCK_SZ + 2][BLOCK_SZ + 2];
  131.     vector <int> off[MAXN], on[MAXN];
  132.  
  133.     void solve(void)
  134.     {
  135.  
  136.         dp[1] = 1;
  137.         FOR(i, 1, n)
  138.         {
  139.             while (on[i].size())
  140.             {
  141.                 int x = on[i].back(); on[i].pop_back();
  142.                 add(lz[x % d[x]][d[x]], dp[x]);
  143.             }
  144.  
  145.             while (off[i].size())
  146.             {
  147.                 int x = off[i].back(); off[i].pop_back();
  148.                 add(lz[x % d[x]][d[x]], MOD - dp[x]);
  149.             }
  150.  
  151.             if (d[i] <= BLOCK_SZ)
  152.                 FOR(D, 1, BLOCK_SZ) add(dp[i], lz[i % D][D]);
  153.  
  154.             if (d[i] > BLOCK_SZ)
  155.             {
  156.                 int t = i;
  157.                 FOR(j, 1, x[i])
  158.                 {
  159.                     t += d[i];
  160.                     if (t > n) break;
  161. //                    assert(t <= n);
  162.                     add(dp[t], dp[i]);
  163.                 }
  164.             }
  165.             else if (d[i])
  166.             {
  167.                 int L = i + d[i], R = min(n, i + x[i] * d[i]);
  168. ////                cout << i << ": " << L << ' ' << R << '\n';
  169.                 on[L].emplace_back(i);
  170.                 off[R + 1].emplace_back(i);
  171.             }
  172.         }
  173.  
  174.         int res = 0;
  175. //        FOR(i, 1, n) cout << dp[i] << ' ';el;
  176.         FOR(i, 1, n) add(res, dp[i]);
  177.         cout << res << '\n';
  178.  
  179.         cerr << 4;
  180.         exit(0);
  181.     }
  182. }
  183.  
  184. signed main(void)
  185. {
  186.     cin.tie(nullptr)->sync_with_stdio(false);
  187. //    cin.exceptions(cin.failbit);
  188.  
  189.     #define task "CUUHO"
  190.     if (fopen(task".INP", "r"))
  191.     {
  192.        freopen(task".INP", "r", stdin);
  193.        freopen(task".OUT", "w", stdout);
  194.     }
  195.     //--OpenFile-------------------------------------------------------------------------------
  196.  
  197.     cin >> n;
  198.     FOR(i, 1, n) cin >> d[i] >> x[i];
  199.  
  200. //    subtask2::solve();
  201. //    subtask1::solve();
  202. //    assert(0);
  203.     subtask4::solve();
  204.  
  205.     cerr << (1.0 * clock() / CLOCKS_PER_SEC);
  206.     return 0;
  207. }
  208.  
Success #stdin #stdout #stderr 0.01s 15180KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
stderr
copy 
4
https://ideone.com/DvN1Mm
language:
C++ (gcc 8.3)
created:
17 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!