fork download
copy 
  1. #include <bits/stdc++.h>
  2. #pragma GCC optimize("O3,unroll-loops")
  3. #define int long long
  4. #define itachi ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  5. #define fi first
  6. #define se second
  7.  
  8. using namespace std;
  9.  
  10. const int MOD = 1e9 + 7;
  11.  
  12. vector<pair<int, int>> dpL, dpR;
  13. vector<int> sufL, sufR;
  14.  
  15. multiset<int> smallVals;
  16. map<int, int> bigVals;
  17.  
  18. int q, L, R;
  19.  
  20. void build_suffix(vector<pair<int, int>> &dp, vector<int> &suf) {
  21.     int n = (int)dp.size();
  22.     suf.assign(n + 1, 0);
  23.     for (int i = n - 1; i >= 0; --i) {
  24.         suf[i] = suf[i + 1] + dp[i].se;
  25.         if (suf[i] >= MOD) suf[i] -= MOD;
  26.     }
  27. }
  28.  
  29. void add_small(vector<pair<int, int>> &dp, vector<int> &suf, int x) {
  30.     if (dp.empty()) return;
  31.  
  32.     if (x == 1) {
  33.         for (auto &p : dp) p.se = (p.se * 2) % MOD;
  34.         build_suffix(dp, suf);
  35.         return;
  36.     }
  37.  
  38.     vector<pair<int, int>> take;
  39.     take.reserve(dp.size());
  40.  
  41.     for (auto &p : dp) {
  42.         if (p.fi >= x) take.push_back({p.fi / x, p.se});
  43.     }
  44.  
  45.     vector<pair<int, int>> nxt;
  46.     nxt.reserve(dp.size() + take.size());
  47.  
  48.     int i = 0, j = 0;
  49.     int n = (int)dp.size(), m = (int)take.size();
  50.  
  51.     while (i < n || j < m) {
  52.         int key;
  53.         if (j == m || (i < n && dp[i].fi < take[j].fi)) key = dp[i].fi;
  54.         else if (i == n || take[j].fi < dp[i].fi) key = take[j].fi;
  55.         else key = dp[i].fi;
  56.  
  57.         int val = 0;
  58.  
  59.         while (i < n && dp[i].fi == key) {
  60.             val += dp[i].se;
  61.             if (val >= MOD) val -= MOD;
  62.             ++i;
  63.         }
  64.         while (j < m && take[j].fi == key) {
  65.             val += take[j].se;
  66.             if (val >= MOD) val -= MOD;
  67.             ++j;
  68.         }
  69.  
  70.         nxt.push_back({key, val});
  71.     }
  72.  
  73.     dp.swap(nxt);
  74.     build_suffix(dp, suf);
  75. }
  76.  
  77. void rebuild(vector<pair<int, int>> &dp, vector<int> &suf, int lim) {
  78.     dp.clear();
  79.     if (lim <= 0) {
  80.         suf.assign(1, 0);
  81.         return;
  82.     }
  83.  
  84.     dp.push_back({lim, 1});
  85.     build_suffix(dp, suf);
  86.  
  87.     for (int x : smallVals) add_small(dp, suf, x);
  88. }
  89.  
  90. vector<pair<int, int>> get_big_distinct() {
  91.     vector<pair<int, int>> b;
  92.     b.reserve(bigVals.size());
  93.     for (auto &it : bigVals) b.push_back({it.fi, it.se});
  94.     return b;
  95. }
  96.  
  97. int solve_limit(vector<pair<int, int>> &dp, vector<int> &suf, int lim) {
  98.     if (lim <= 0 || dp.empty()) return 0;
  99.  
  100.     vector<pair<int, int>> b = get_big_distinct();
  101.     vector<pair<int, int>> bigquery;
  102.     bigquery.reserve(1 + (int)b.size() * 8);
  103.  
  104.     auto addq = [&](int prod, int ways) {
  105.         if (prod <= lim) bigquery.push_back({prod, ways % MOD});
  106.     };
  107.  
  108.     addq(1, 1);
  109.  
  110.     int m = (int)b.size();
  111.  
  112.     for (int i = 0; i < m; ++i) {
  113.         int v = b[i].fi, c = b[i].se;
  114.  
  115.         if (v <= lim) addq(v, c);
  116.  
  117.         if (c >= 2 && v <= lim / v) {
  118.             int ways = (c * (c - 1) / 2) % MOD;
  119.             addq(v * v, ways);
  120.         }
  121.  
  122.         if (c >= 3 && v <= lim / v / v) {
  123.             int ways = (c * (c - 1) * (c - 2) / 6) % MOD;
  124.             addq(v * v * v, ways);
  125.         }
  126.  
  127.         for (int j = i + 1; j < m; ++j) {
  128.             int u = b[j].fi, d = b[j].se;
  129.  
  130.             if (v > lim / u) break;
  131.  
  132.             int ways12 = (c * d) % MOD;
  133.             int prod12 = v * u;
  134.             addq(prod12, ways12);
  135.  
  136.             if (c >= 2 && prod12 <= lim / v) {
  137.                 int ways = (c * (c - 1) / 2) % MOD;
  138.                 ways = (ways * d) % MOD;
  139.                 addq(v * v * u, ways);
  140.             }
  141.  
  142.             if (d >= 2 && prod12 <= lim / u) {
  143.                 int ways = (d * (d - 1) / 2) % MOD;
  144.                 ways = (ways * c) % MOD;
  145.                 addq(v * u * u, ways);
  146.             }
  147.  
  148.             for (int k = j + 1; k < m; ++k) {
  149.                 int w = b[k].fi, e = b[k].se;
  150.                 if (prod12 > lim / w) break;
  151.  
  152.                 int ways = c;
  153.                 ways = (ways * d) % MOD;
  154.                 ways = (ways * e) % MOD;
  155.                 addq(prod12 * w, ways);
  156.             }
  157.         }
  158.     }
  159.  
  160.     sort(bigquery.begin(), bigquery.end());
  161.  
  162.     vector<pair<int, int>> comp;
  163.     comp.reserve(bigquery.size());
  164.  
  165.     for (auto &p : bigquery) {
  166.         if (comp.empty() || comp.back().fi != p.fi) comp.push_back(p);
  167.         else {
  168.             comp.back().se += p.se;
  169.             if (comp.back().se >= MOD) comp.back().se -= MOD;
  170.         }
  171.     }
  172.  
  173.     int ans = 0;
  174.     int p = 0, n = (int)dp.size();
  175.  
  176.     for (auto &qv : comp) {
  177.         int need = qv.fi;
  178.         int ways = qv.se;
  179.  
  180.         while (p < n && dp[p].fi < need) ++p;
  181.  
  182.         ans += (suf[p] * ways) % MOD;
  183.         if (ans >= MOD) ans -= MOD;
  184.     }
  185.  
  186.     return ans;
  187. }
  188.  
  189. signed main() {
  190.     itachi
  191.  
  192.     freopen("CPROD.inp", "r", stdin);
  193.     freopen("CPROD.out", "w", stdout);
  194.  
  195.     cin >> q >> L >> R;
  196.  
  197.     rebuild(dpL, sufL, L - 1);
  198.     rebuild(dpR, sufR, R);
  199.  
  200.     while (q--) {
  201.         char opt;
  202.         int x;
  203.         cin >> opt >> x;
  204.  
  205.         if (x <= 180) {
  206.             if (opt == '+') {
  207.                 smallVals.insert(x);
  208.                 add_small(dpL, sufL, x);
  209.                 add_small(dpR, sufR, x);
  210.             } else {
  211.                 auto it = smallVals.find(x);
  212.                 if (it != smallVals.end()) {
  213.                     smallVals.erase(it);
  214.                     rebuild(dpL, sufL, L - 1);
  215.                     rebuild(dpR, sufR, R);
  216.                 }
  217.             }
  218.         } else {
  219.             if (opt == '+') {
  220.                 bigVals[x]++;
  221.             } else {
  222.                 auto it = bigVals.find(x);
  223.                 if (it != bigVals.end()) {
  224.                     if (--it->se == 0) bigVals.erase(it);
  225.                 }
  226.             }
  227.         }
  228.  
  229.         int ansR = solve_limit(dpR, sufR, R);
  230.         int ansL = solve_limit(dpL, sufL, L - 1);
  231.  
  232.         int ans = ansR - ansL;
  233.         if (ans < 0) ans += MOD;
  234.  
  235.         cout << ans << '\n';
  236.     }
  237.  
  238.     return 0;
  239. }
  240.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0jUgqS
language:
C++14 (gcc 8.3)
created:
6 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!