fork(1) download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. using namespace __gnu_pbds;
  6.  
  7. typedef long long ll;
  8. random_device rd;
  9. mt19937 rng(0);
  10. uniform_int_distribution<ll> uni(1, 1e9);
  11. typedef pair<ll, ll> pii;
  12.  
  13. const ll rdseed = (uint64_t)(make_unique<char>().get()) ^ chrono::high_resolution_clock::now().time_since_epoch().count();
  14.  
  15. const ll N = 1e18;
  16. const ll NUM_ELEM = 2e5;
  17. const ll NUM_QUERIES = 2e5;
  18. struct Node {
  19. Node *lp, *rp;
  20. ll sum;
  21. };
  22. inline ll eval(Node *p) { return p ? p->sum : 0LL; }
  23.  
  24. const ll bufSize = NUM_ELEM * 31;
  25. Node buf[bufSize];
  26. Node *newNode() {
  27. static auto ptr = buf;
  28. return ptr++;
  29. }
  30.  
  31. ll getSum(Node *cur, ll l, ll r, ll x, ll y) {
  32. if (!cur || x > r || y < l)
  33. return 0;
  34. if (x <= l && r <= y) {
  35. return cur->sum;
  36. }
  37. ll m = (l + r) / 2;
  38. return getSum(cur->lp, l, m, x, y) + getSum(cur->rp, m + 1, r, x, y);
  39. }
  40. void update(Node *&cur, ll l, ll r, ll pos, ll val) {
  41. if (!cur)
  42. cur = newNode();
  43. if (l == r) {
  44. cur->sum = val;
  45. } else {
  46. ll m = (l + r) / 2;
  47. if (pos <= m) {
  48. update(cur->lp, l, m, pos, val);
  49. } else {
  50. update(cur->rp, m + 1, r, pos, val);
  51. }
  52. cur->sum = eval(cur->lp) + eval(cur->rp);
  53. }
  54. }
  55. Node *root;
  56.  
  57. uint64_t hash_f(uint64_t x) {
  58. x ^= x >> 33;
  59. x *= 0xff51afd7ed558ccd;
  60. x ^= x >> 33;
  61. x *= 0xc4ceb9fe1a85ec53;
  62. x ^= x >> 33;
  63. return x;
  64. }
  65. class custom_size_policy : public hash_exponential_size_policy<size_t> {
  66. public:
  67. custom_size_policy() : hash_exponential_size_policy(1 << 24, 2) {}
  68. };
  69.  
  70. struct chash {
  71. ll operator()(ll x) const { return hash_f(x); }
  72. };
  73.  
  74. typedef gp_hash_table<ll, ll, chash, equal_to<ll>, direct_mask_range_hashing<ll>, linear_probe_fn<>,
  75. hash_standard_resize_policy<custom_size_policy, hash_load_check_resize_trigger<true>, true>>
  76. gp;
  77.  
  78. gp seg;
  79. ll get(ll x) {
  80. auto res = seg.find(x);
  81. return (res == seg.end()) ? 0 : res->second;
  82. }
  83. void modify(ll p, ll val) {
  84. for (seg[p += N] = val; p > 0; p >>= 1) {
  85. seg[p >> 1] = get(p) + get(p ^ 1);
  86. }
  87. }
  88.  
  89. ll query(ll l, ll r) {
  90. ll res = 0;
  91. for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
  92. if (l & 1)
  93. res += get(l++);
  94. if (r & 1)
  95. res += get(--r);
  96. }
  97. return res;
  98. }
  99.  
  100. signed main() {
  101. ios::sync_with_stdio(0);
  102. cin.tie(0);
  103. vector<pii> elems;
  104. for (ll i = 0; i < NUM_ELEM; i++) {
  105. elems.push_back({uni(rng), uni(rng)});
  106. }
  107. vector<pii> queries;
  108. for (ll i = 0; i < NUM_QUERIES; i++) {
  109. ll a = uni(rng), b = uni(rng);
  110. if (a > b)
  111. swap(a, b);
  112. queries.push_back({a, b});
  113. }
  114. vector<ll> ans1, ans2;
  115. clock_t begin;
  116. begin = clock();
  117. for (auto i : elems) {
  118. modify(i.first, i.second);
  119. }
  120. for (auto i : queries) {
  121. ans2.push_back(query(i.first, i.second + 1));
  122. }
  123. cout << "hash: " << (double)(clock() - begin) / CLOCKS_PER_SEC << endl;
  124. seg.clear();
  125.  
  126. begin = clock();
  127. for (auto i : elems) {
  128. update(root, 1, N, i.first, i.second);
  129. }
  130. for (auto i : queries) {
  131. ans1.push_back(getSum(root, 1, N, i.first, i.second));
  132. }
  133. cout << "pointer: " << (double)(clock() - begin) / CLOCKS_PER_SEC << endl;
  134. for (ll i = 0; i < ans1.size(); i++) {
  135. assert(ans1[i] == ans2[i]);
  136. }
  137. }
Success #stdin #stdout 0.97s 160704KB
stdin
Standard input is empty
stdout
hash: 0.512258
pointer: 0.317112