fork download 
  1. #include <bits/stdc++.h>
  2. #pragma GCC optimize("O3,unroll-loops")
  3. #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  4.  
  5. #define int long long
  6. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  7.  
  8. using namespace std;
  9.  
  10. const int mod = 1e9 + 7;
  11.  
  12. // ===== STATE L =====
  13. int limL;
  14. vector<pair<int,int>> dpL;
  15. vector<int> sufL;
  16.  
  17. // ===== STATE R =====
  18. int limR;
  19. vector<pair<int,int>> dpR;
  20. vector<int> sufR;
  21.  
  22. multiset<int> smalls;
  23. map<int,int> big;
  24.  
  25. // ===== INIT =====
  26. void initL(int lim){
  27.     limL = lim;
  28.     dpL.clear();
  29.     sufL.clear();
  30.     if(limL >= 0){
  31.         dpL.push_back({limL,1});
  32.         sufL = {0,1};
  33.     }
  34. }
  35.  
  36. void initR(int lim){
  37.     limR = lim;
  38.     dpR.clear();
  39.     sufR.clear();
  40.     if(limR >= 0){
  41.         dpR.push_back({limR,1});
  42.         sufR = {0,1};
  43.     }
  44. }
  45.  
  46. // ===== BUILD SUFFIX =====
  47. void build_suf(vector<pair<int,int>> &dp, vector<int> &suf){
  48.     int sz = dp.size();
  49.     suf.assign(sz+1,0);
  50.     for(int i=sz-1;i>=0;i--){
  51.         suf[i] = (suf[i+1] + dp[i].second) % mod;
  52.     }
  53. }
  54.  
  55. // ===== ADD SMALL =====
  56. void add_small(vector<pair<int,int>> &dp, vector<int> &suf, int x){
  57.     if(x <= 1) return;
  58.  
  59.     unordered_map<int,int> nxt;
  60.  
  61.     for(auto &p : dp){
  62.         nxt[p.first] = (nxt[p.first] + p.second) % mod;
  63.         if(p.first >= x){
  64.             int v = p.first / x;
  65.             nxt[v] = (nxt[v] + p.second) % mod;
  66.         }
  67.     }
  68.  
  69.     dp.clear();
  70.     for(auto &p : nxt) dp.push_back(p);
  71.     sort(dp.begin(), dp.end());
  72.  
  73.     build_suf(dp, suf);
  74. }
  75.  
  76. // ===== REBUILD =====
  77. void rebuild(vector<pair<int,int>> &dp, vector<int> &suf, int lim){
  78.     unordered_map<int,int> cur;
  79.     cur[lim] = 1;
  80.  
  81.     for(int x : smalls){
  82.         unordered_map<int,int> nxt = cur;
  83.         for(auto &p : cur){
  84.             if(p.first >= x){
  85.                 int v = p.first / x;
  86.                 nxt[v] = (nxt[v] + p.second) % mod;
  87.             }
  88.         }
  89.         cur = nxt;
  90.     }
  91.  
  92.     dp.clear();
  93.     for(auto &p : cur) dp.push_back(p);
  94.     sort(dp.begin(), dp.end());
  95.  
  96.     build_suf(dp, suf);
  97. }
  98.  
  99. // ===== QUERY =====
  100. int calc(vector<pair<int,int>> &dp, vector<int> &suf, vector<int> &bigp){
  101.     int total = suf[0];
  102.     int p = 0;
  103.     int sz = dp.size();
  104.  
  105.     for(int i = (int)bigp.size()-1; i>=0; i--){
  106.         while(p < sz && dp[p].first < bigp[i]) p++;
  107.         if(p < sz) total = (total + suf[p]) % mod;
  108.     }
  109.     return total;
  110. }
  111.  
  112. // ===== SOLVE =====
  113. void solve(){
  114.     int q,L,R;
  115.     cin >> q >> L >> R;
  116.  
  117.     initL(L-1);
  118.     initR(R);
  119.  
  120.     while(q--){
  121.         char op; int x;
  122.         cin >> op >> x;
  123.  
  124.         if(x <= 180){
  125.             if(op == '+'){
  126.                 smalls.insert(x);
  127.                 add_small(dpL, sufL, x);
  128.                 add_small(dpR, sufR, x);
  129.             }else{
  130.                 auto it = smalls.find(x);
  131.                 if(it != smalls.end()){
  132.                     smalls.erase(it);
  133.                     rebuild(dpL, sufL, L-1);
  134.                     rebuild(dpR, sufR, R);
  135.                 }
  136.             }
  137.         }else{
  138.             if(op == '+') big[x]++;
  139.             else{
  140.                 if(big[x]){
  141.                     big[x]--;
  142.                     if(big[x] == 0) big.erase(x);
  143.                 }
  144.             }
  145.         }
  146.  
  147.         // ===== build big products =====
  148.         vector<int> bigp;
  149.         vector<pair<int,int>> b(big.begin(), big.end());
  150.  
  151.         int n = b.size();
  152.  
  153.         for(int i=0;i<n;i++){
  154.             int v1 = b[i].first;
  155.             for(int c1=1;c1<=min(3LL,b[i].second);c1++){
  156.                 int p1 = 1;
  157.                 bool ok = 1;
  158.                 for(int k=0;k<c1;k++){
  159.                     if(p1 > R / v1){ ok=0; break; }
  160.                     p1 *= v1;
  161.                 }
  162.                 if(!ok) break;
  163.  
  164.                 bigp.push_back(p1);
  165.  
  166.                 for(int j=i+1;j<n;j++){
  167.                     int v2 = b[j].first;
  168.                     int p2 = p1;
  169.  
  170.                     for(int c2=1;c2<=min(3LL-c1,b[j].second);c2++){
  171.                         if(p2 > R / v2) break;
  172.                         p2 *= v2;
  173.                         bigp.push_back(p2);
  174.  
  175.                         if(c1 + c2 < 3){
  176.                             for(int k=j+1;k<n;k++){
  177.                                 if(p2 <= R / b[k].first)
  178.                                     bigp.push_back(p2 * b[k].first);
  179.                             }
  180.                         }
  181.                     }
  182.                 }
  183.             }
  184.         }
  185.  
  186.         sort(bigp.begin(), bigp.end());
  187.  
  188.         int ansR = calc(dpR, sufR, bigp);
  189.         int ansL = calc(dpL, sufL, bigp);
  190.  
  191.         cout << (ansR - ansL + mod) % mod << '\n';
  192.     }
  193. }
  194.  
  195. signed main(){
  196.     itachi
  197.     freopen("CPROD.inp","r",stdin);
  198.     freopen("CPROD.out","w",stdout);
  199.  
  200.     solve();
  201. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/7z8qYq
language:
C++14 (gcc 8.3)
created:
7 days 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!