fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const long long MOD = 1e9 + 7;
  9.  
  10. // Lũy thừa nhị phân tối ưu
  11. long long power(long long base, long long exp) {
  12.     long long res = 1;
  13.     base %= MOD;
  14.     while (exp > 0) {
  15.         if (exp % 2 == 1) res = (res * base) % MOD;
  16.         base = (base * base) % MOD;
  17.         exp /= 2;
  18.     }
  19.     return res;
  20. }
  21.  
  22. // Hàm sinh và sắp xếp các key cho unordered_map
  23. vector<long long> generate_keys(long long X) {
  24.     vector<long long> keys;
  25.     keys.push_back(0); // Trạng thái 0 (tích vượt quá X)
  26.     if (X == 0) return keys;
  27.  
  28.     for (long long i = 1; i <= X; ) {
  29.         long long q = X / i;
  30.         keys.push_back(q);
  31.         long long next_i = X / q + 1;
  32.         i = next_i;
  33.     }
  34.     // Sort bắt buộc để duyệt đúng chiều DP Knapsack
  35.     sort(keys.begin(), keys.end()); 
  36.     return keys;
  37. }
  38.  
  39. int main() {
  40.     ios_base::sync_with_stdio(false);
  41.     cin.tie(NULL);
  42.  
  43.     int Q;
  44.     long long L, R;
  45.     if (!(cin >> Q >> L >> R)) return 0;
  46.  
  47.     // Sinh keys
  48.     vector<long long> keysR = generate_keys(R);
  49.     vector<long long> keysL = generate_keys(L - 1);
  50.  
  51.     // Sử dụng unordered_map theo đúng định hướng
  52.     unordered_map<long long, long long> dpR;
  53.     unordered_map<long long, long long> dpL;
  54.  
  55.     // Khởi tạo Base Case (Tập rỗng có tích = 1, luôn <= k với mọi k >= 1)
  56.     for (long long k : keysR) if (k > 0) dpR[k] = 1;
  57.     for (long long k : keysL) if (k > 0) dpL[k] = 1;
  58.  
  59.     long long cnt1 = 0;
  60.  
  61.     while (Q--) {
  62.         char type;
  63.         long long x;
  64.         cin >> type >> x;
  65.  
  66.         if (type == '+') {
  67.             if (x == 1) {
  68.                 cnt1++;
  69.             } else {
  70.                 // Thêm: Duyệt từ lớn xuống bé
  71.                 for (int i = keysR.size() - 1; i >= 0; --i) {
  72.                     long long v = keysR[i];
  73.                     dpR[v] = (dpR[v] + dpR[v / x]) % MOD;
  74.                 }
  75.                 if (L > 1) {
  76.                     for (int i = keysL.size() - 1; i >= 0; --i) {
  77.                         long long v = keysL[i];
  78.                         dpL[v] = (dpL[v] + dpL[v / x]) % MOD;
  79.                     }
  80.                 }
  81.             }
  82.         } 
  83.         else if (type == '-') {
  84.             if (x == 1) {
  85.                 cnt1--;
  86.             } else {
  87.                 // Xoá (Rollback): Duyệt từ bé lên lớn
  88.                 for (size_t i = 0; i < keysR.size(); ++i) {
  89.                     long long v = keysR[i];
  90.                     dpR[v] = (dpR[v] - dpR[v / x] + MOD) % MOD;
  91.                 }
  92.                 if (L > 1) {
  93.                     for (size_t i = 0; i < keysL.size(); ++i) {
  94.                         long long v = keysL[i];
  95.                         dpL[v] = (dpL[v] - dpL[v / x] + MOD) % MOD;
  96.                     }
  97.                 }
  98.             }
  99.         }
  100.  
  101.         // Tính kết quả
  102.         long long ansR = dpR[R];
  103.         long long ansL = (L > 1) ? dpL[L - 1] : 0;
  104.  
  105.         long long final_ans = (ansR - ansL + MOD) % MOD;
  106.         final_ans = (final_ans * power(2, cnt1)) % MOD;
  107.  
  108.         cout << final_ans << "\n";
  109.     }
  110.  
  111.     return 0;
  112. }
Success #stdin #stdout 0.16s 10740KB
comments (?)
stdin
copy 
20 999999999 1000000000
+ 2
+ 3
+ 2
+ 4
+ 5
+ 2
+ 3
+ 7
+ 11
+ 13
+ 2
+ 3
+ 5
+ 17
+ 19
+ 2
+ 2
+ 3
+ 23
+ 29
stdout
copy 
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
https://ideone.com/ukz9zS
language:
C++14 (gcc 8.3)
created:
4 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!